Advertisement
mickypinata

CUBE-T180: Destruction

Sep 12th, 2021
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 5e4;
  7. const int K = 1000;
  8.  
  9. lli qs[N + 1], dp[N + 1][2];
  10.  
  11. int main(){
  12.  
  13.     int n, parts, m;
  14.     scanf("%d%d%d", &n, &parts, &m);
  15.     for(int i = 1; i <= n; ++i){
  16.         scanf("%lld", &qs[i]);
  17.         qs[i] += qs[i - 1];
  18.     }
  19.     for(int i = 0; i <= n; ++i){
  20.         dp[i][0] = 0;
  21.     }
  22.     for(int p = 1; p <= parts; ++p){
  23.         int cur = p % 2;
  24.         int prv = cur ^ 1;
  25.         dp[0][cur] = 1e18;
  26.         lli pm1 = 1e18;
  27.         lli pm2 = 1e18;
  28.         for(int i = 1; i <= n; ++i){
  29.             if(i - m + 1 > 0){
  30.                 if(i - m + 1 == 1){
  31.                     pm1 = min(pm1, p == 1 ? 0 : (lli)1e18);
  32.                 } else {
  33.                     pm1 = min(pm1, dp[i - m - 1][prv] - qs[i - m]);
  34.                 }
  35.             }
  36.             if(i >= m){
  37.                 pm2 = min(pm2, qs[i] + pm1);
  38.             }
  39.             dp[i][cur] = pm2;
  40.         }
  41.     }
  42.     cout << qs[n] - dp[n][parts % 2];
  43.  
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement