matheus_monteiro

Etiquetas

Jun 9th, 2021
319
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.72 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define OO 0x3f3f3f3f
  4.  
  5. int n, k, c;
  6. int pf[30000];
  7. int mini[30000];
  8. int dp[30000];
  9.  
  10. int sum(int l, int r) {
  11.     return pf[r] - pf[l - 1];
  12. }
  13.  
  14. int main() {
  15.     cin >> n >> k >> c;
  16.     for(int i = 1; i <= n; i++)
  17.         cin >> pf[i], pf[i] += pf[i - 1];
  18.     for(int i = 0; i <= n; i++)
  19.         mini[i] = dp[i] = OO;
  20.     for(int i = c; i <= n; i++) {
  21.         dp[i] = sum(i - c + 1, i);
  22.         mini[i] = min(mini[i - 1], dp[i]);
  23.     }
  24.     for(int i = 2; i <= k; i++) {
  25.         for(int j = i * c; j <= n; j++)
  26.             dp[j] = mini[j - c] + sum(j - c + 1, j);
  27.         mini[i * c] = dp[i * c];
  28.         for(int j = i * c + 1; j <= n; j++)
  29.             mini[j] = min(mini[j - 1], dp[j]);
  30.     }
  31.     cout << pf[n] - mini[n] << '\n';
  32.  
  33.     return 0;
  34. }
  35.  
Advertisement
Add Comment
Please, Sign In to add comment