# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1094220 | Trisanu_Das | Feast (NOI19_feast) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2005][2005];
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k; cin >> n >> k;
int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) a[i] += a[i - 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k; j++){
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
for(int l = 0; l < i; l++) dp[i][j] = max(dp[i][j], dp[l][j - 1] + a[i] - a[l];
}
}
cout << dp[n][k];
}