fork download 
  1. /**            
  2.  * author      minhnguyent546
  3.  * created_at  Sat, 2025-11-08 07:32:27
  4.  **/           
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #ifdef LOCAL
  9. #include "cp/debug.h"
  10. #else
  11. #define debug(...)
  12. #define cerr if (false) cerr
  13. #endif
  14.  
  15. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  16. #define yay exit(EXIT_SUCCESS)
  17. #define panik exit(EXIT_FAILURE)
  18.  
  19. const int INF = 0x3f3f3f3f;
  20. const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
  21.  
  22. #define bit(mask, i) (((mask) >> (i)) & 1)
  23.  
  24. int n, k;
  25. vector<int> arr;
  26. void read() {
  27.     cin >> n >> k;
  28.     if (n < 1 || n > (int) 2e5) {
  29.         eprintf("Expected n is in range [1, 2e5], found %d\n", n);
  30.         panik;
  31.     }
  32.     if (k < 1 || k * 2 > (n + 1)) {
  33.         eprintf("Expected k is in range [1, (n+1)/2], found %d\n", k);
  34.         panik;
  35.     }
  36.     arr.resize(n);
  37.     for (int i = 0; i < n; ++i) {
  38.         cin >> arr[i];
  39.         if (arr[i] < -(int) 1e9 || arr[i] > (int) 1e9) {
  40.             eprintf("Expected arr[%d] is in range [-1e9, 1e9], found %d\n", i, arr[i]);
  41.             panik;
  42.         }
  43.     }
  44. }
  45.  
  46. namespace sub1 {
  47.     bool check() {
  48.         return n <= 20;
  49.     }
  50.  
  51.     void solve() {
  52.         cerr << " *** [sub1] *** " << '\n';
  53.  
  54.         long long ans = -INF_LL;
  55.         for (int mask = 0; mask < (1 << n); ++mask) {
  56.             if (__builtin_popcount(mask) != k) continue;
  57.             bool valid = true;
  58.             for (int i = 0; i < n - 1; ++i) {
  59.                 if (bit(mask, i) && bit(mask, i + 1)) {
  60.                     valid = false;
  61.                     break;
  62.                 }
  63.             }
  64.             if (!valid) continue;
  65.             long long cur = 0;
  66.             for (int i = 0; i < n; ++i) {
  67.                 if (bit(mask, i)) cur += arr[i];
  68.             }
  69.             ans = max(ans, cur);
  70.         }
  71.         cout << ans << '\n';
  72.     }
  73. } // namespace sub1
  74.  
  75.  
  76. namespace sub2 {
  77.     bool check() {
  78.         return k == 2;
  79.     }
  80.  
  81.     void solve() {
  82.         cerr << " *** [sub2] *** " << '\n';
  83.  
  84.         int ans = INT_MIN;
  85.         int max_prev = -INF;
  86.         for (int i = 1; i < n; ++i) {
  87.             ans = max(ans, arr[i] + max_prev);
  88.             max_prev = max(max_prev, arr[i - 1]);
  89.         }
  90.         cout << ans << '\n';
  91.  
  92.     }
  93. } // namespace sub2
  94.  
  95.  
  96. namespace sub3 {
  97.     bool check() {
  98.         return k == 3;
  99.     }
  100.  
  101.     void solve() {
  102.         cerr << " *** [sub3] *** " << '\n';
  103.  
  104.         vector<int> max_left(n), max_right(n);
  105.         max_left[0] = arr[0];
  106.         for (int i = 1; i < n; ++i) {
  107.             max_left[i] = max(max_left[i - 1], arr[i]);
  108.         }
  109.         max_right[n - 1] = arr[n - 1];
  110.         for (int i = n - 2; i >= 0; --i) {
  111.             max_right[i] = max(max_right[i + 1], arr[i]);
  112.         }
  113.  
  114.         long long ans = -INF_LL;
  115.         for (int i = 2; i < n - 2; ++i) {
  116.             ans = max(ans, (long long) arr[i] + max_left[i - 2] + max_right[i + 2]);
  117.         }
  118.         cout << ans << '\n';
  119.     }
  120. } // namespace sub3
  121.  
  122.  
  123. namespace sub4 {
  124.     bool check() {
  125.         return n <= (int) 1e3;
  126.     }
  127.  
  128.     void solve() {
  129.         cerr << " *** [sub4] *** " << '\n';
  130.  
  131.         vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, -INF_LL));
  132.         vector<long long> max_sofar(n + 1);
  133.         for (int i = 1; i <= n; ++i) {
  134.             dp[1][i] = max(dp[1][i - 1], (long long) arr[i - 1]);
  135.         }
  136.         for (int j = 2; j <= k; ++j) {
  137.             max_sofar[0] = dp[j - 1][0];
  138.             for (int i = 1; i <= n; ++i) {
  139.                 max_sofar[i] = max(max_sofar[i - 1], dp[j - 1][i]);
  140.             }
  141.             for (int i = 1; i <= n; ++i) {
  142.                 // ignore a_i
  143.                 dp[j][i] = dp[j][i - 1];
  144.  
  145.                 // add a_i
  146.                 // for (int z = 0; z <= i - 2; ++z) {
  147.                 //     dp[j][i] = max(dp[j][i], dp[j - 1][z] + arr[i - 1]);
  148.                 // }
  149.                 if (i - 2 >= 0) dp[j][i] = max(dp[j][i], max_sofar[i - 2] + arr[i - 1]);
  150.             }
  151.         }
  152.         cout << dp[k][n] << '\n';
  153.  
  154.     }
  155. } // namespace sub4
  156.  
  157.  
  158. namespace sub5 {
  159.     bool check() {
  160.         return k == n / 2 && (n % 2 == 0);
  161.     }
  162.  
  163.     void solve() {
  164.         cerr << " *** [sub5] *** " << '\n';
  165.  
  166.         int sz = n / 2;
  167.         vector<array<long long, 2>> dp(sz, {-INF_LL, -INF_LL});
  168.  
  169.         dp[0][0] = arr[0];
  170.         dp[0][1] = arr[1];
  171.         for (int i = 1; i < sz; ++i) {
  172.             dp[i][0] = dp[i - 1][0] + arr[i * 2];
  173.             dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i * 2 + 1];
  174.         }
  175.         cout << max(dp[sz - 1][0], dp[sz - 1][1]) << '\n';
  176.     }
  177. } // namespace sub5
  178.  
  179.  
  180. namespace sub6 {
  181.     bool check() {
  182.         return k == (n + 1) / 2 && (n & 1);
  183.     }
  184.  
  185.     void solve() {
  186.         cerr << " *** [sub6] *** " << '\n';
  187.  
  188.         if (n == 1) {
  189.             cout << arr[0] << '\n';
  190.             return;
  191.         }
  192.         int sz = n / 2;
  193.         vector<array<long long, 2>> dp(sz, {-INF_LL, -INF_LL});
  194.         vector<array<long long, 2>> rdp(sz, {-INF_LL, -INF_LL});
  195.         vector<int> rarr(arr.begin(), arr.end());
  196.         rarr.pop_back();
  197.         reverse(rarr.begin(), rarr.end());
  198.  
  199.         dp[0][0] = arr[0];
  200.         dp[0][1] = arr[1];
  201.         rdp[0][1] = rarr[1];
  202.         for (int i = 1; i < sz; ++i) {
  203.             dp[i][0] = dp[i - 1][0] + arr[i * 2];
  204.             rdp[i][0] = rdp[i - 1][0] + rarr[i * 2];
  205.             dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i * 2 + 1];
  206.             debug(n, sz, i * 2 + 1);
  207.             assert(i * 2 + 1 < n - 1);
  208.             rdp[i][1] = max(rdp[i - 1][0], rdp[i - 1][1]) + rarr[i * 2 + 1];
  209.         }
  210.         // ignore arr[n - 1]
  211.         long long ans = max(dp[sz - 1][0], dp[sz - 1][1]);
  212.  
  213.         // add arr[n - 1], must remove one pair
  214.         if (sz == 1) {
  215.             ans = max(ans, 1LL * arr[n - 1]);
  216.         } else {
  217.             for (int i = 0; i < sz; ++i) {
  218.                 if (i == 0) {
  219.                     ans = max(ans, max(rdp[sz - 2][0], rdp[sz - 2][1]) + arr[n - 1]);
  220.                 } else if (i == sz - 1) {
  221.                     ans = max(ans, max(dp[sz - 2][0], dp[sz - 2][1]) + arr[n - 1]);
  222.                 } else {
  223.                     ans = max(ans, (max(dp[i - 1][0], dp[i - 1][1]) + max(rdp[sz - i - 2][0], rdp[sz - i - 2][1])) + arr[n - 1]);
  224.                 }
  225.             }
  226.         }
  227.         cout << ans << '\n';
  228.     }
  229. } // namespace sub6
  230.  
  231.  
  232. namespace sub7 {
  233.     bool check() {
  234.         return true;
  235.     }
  236.  
  237.     void solve() {
  238.         cerr << " *** [sub7] *** " << '\n';
  239.  
  240.         vector<long long> dp(n + 1, INF);
  241.         vector<int> min_cnt(n + 1, 0);
  242.         auto gud = [&](int lambda) {
  243.             dp[0] = 0;
  244.             min_cnt[0] = 0;
  245.             if (arr[0] - lambda >= 0) {
  246.                 dp[1] = arr[0] - lambda;
  247.                 min_cnt[1] = 1;
  248.             } else {
  249.                 dp[1] = 0;
  250.                 min_cnt[1] = 0;
  251.             }
  252.             for (int i = 2; i <= n; ++i) {
  253.                 // ignore a_i
  254.                 dp[i] = dp[i - 1];
  255.                 min_cnt[i] = min_cnt[i - 1];
  256.  
  257.                 // add a_i
  258.                 long long nval = dp[i - 2] + arr[i - 1] - lambda;
  259.                 if (nval > dp[i]) {
  260.                     dp[i] = nval;
  261.                     min_cnt[i] = min_cnt[i - 2] + 1;
  262.                 } else if (nval == dp[i]) {
  263.                     min_cnt[i] = max(min_cnt[i], min_cnt[i - 2] + 1);
  264.                 }
  265.  
  266.             }
  267.             // return min_cnt[n] >= k;
  268.             return min_cnt[n] >= k;
  269.         };
  270.  
  271.         int inf = (int) 1e9;
  272.         int l = -inf - 3, r = inf + 3;
  273.         while (l < r) {
  274.             int mid = l + (r - l + 1) / 2;
  275.             if (gud(mid)) {
  276.                 l = mid;
  277.             } else {
  278.                 r = mid - 1;
  279.             }
  280.         }
  281.  
  282.         gud(l);
  283.         cout << dp[n] + 1LL * k * l << '\n';
  284.  
  285.     }
  286. } // namespace sub7
  287.  
  288.  
  289.  
  290.  
  291. int main() {
  292.     cin.tie(nullptr)->sync_with_stdio(false);
  293.     cin.exceptions(cin.failbit);
  294.     read();
  295.  
  296.     sub7::solve(); yay;
  297.  
  298.     #ifdef LOCAL
  299.         sub5::solve(); yay;
  300.         sub6::solve(); yay;
  301.         sub7::solve(); yay;
  302.         sub4::solve(); yay;
  303.         sub3::solve(); yay;
  304.         sub2::solve(); yay;
  305.         sub1::solve(); yay;
  306.     #endif
  307.  
  308.     if (sub1::check()) {
  309.         sub1::solve(); yay;
  310.     }        
  311.     if (sub2::check()) {
  312.         sub2::solve(); yay;
  313.     }        
  314.     if (sub3::check()) {
  315.         sub3::solve(); yay;
  316.     }        
  317.     if (sub4::check()) {
  318.         sub4::solve(); yay;
  319.     }
  320.     if (sub5::check()) {
  321.         sub5::solve(); yay;
  322.     }
  323.     if (sub6::check()) {
  324.         sub6::solve(); yay;
  325.     }
  326.     if (sub7::check()) {
  327.         sub7::solve(); yay;
  328.     }
  329.  
  330.     return 0;
  331. }
  332.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 3
3 -2 1 4 5
stdout 
9
https://ideone.com/kuPaGA
[CICT CPC 2025 - FluxLabs] Chiên da săn kho báu (Lambda optimization)

Problem link: https://d...content-available-to-author-only...u.vn/problem/1011
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!