Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define OO 0x3f3f3f3f
- int n, k, c;
- int pf[30000];
- int mini[30000];
- int dp[30000];
- int sum(int l, int r) {
- return pf[r] - pf[l - 1];
- }
- int main() {
- cin >> n >> k >> c;
- for(int i = 1; i <= n; i++)
- cin >> pf[i], pf[i] += pf[i - 1];
- for(int i = 0; i <= n; i++)
- mini[i] = dp[i] = OO;
- for(int i = c; i <= n; i++) {
- dp[i] = sum(i - c + 1, i);
- mini[i] = min(mini[i - 1], dp[i]);
- }
- for(int i = 2; i <= k; i++) {
- for(int j = i * c; j <= n; j++)
- dp[j] = mini[j - c] + sum(j - c + 1, j);
- mini[i * c] = dp[i * c];
- for(int j = i * c + 1; j <= n; j++)
- mini[j] = min(mini[j - 1], dp[j]);
- }
- cout << pf[n] - mini[n] << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment