Submission #1000298

#TimeUsernameProblemLanguageResultExecution timeMemory
1000298nngan267Feast (NOI19_feast)C++17
41 / 100
11 ms27300 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define db long double #define ii pair<int, int> #define fi first #define se second const int maxn = 2005; const ll mod = 111539786; const db eps = -1e9; const ll inf = 1e18; int n, k; int a[maxn]; ll dp[maxn][maxn]; ll s[maxn]; void solve(){ cin >> n >> k; for(int i=1; i<=n; i++){ cin >> a[i]; s[i] = s[i-1] + a[i]; } for(int i=1; i<=k; i++){ ll max_val = 0; for(int j=1; j<=n; j++){ dp[i][j] = dp[i][j-1]; dp[i][j] = max(dp[i][j], max_val + s[j]); max_val = max(max_val, dp[i-1][j] - s[j]); } } cout << dp[k][n] << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int test = 1; while(test--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...