Submission #1025668

#TimeUsernameProblemLanguageResultExecution timeMemory
1025668fv3Feast (NOI19_feast)C++14
0 / 100
718 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, K; cin >> N >> K; vector<ll> a(N); for (int i = 0; i < N; i++) cin >> a[i]; // Maximize satisfaction with 1, then 2, then ... segments vector<vector<ll>> dp(K+1, vector<ll>(N)); vector<vector<ll>> mx(K+1, vector<ll>(N)); for (int k = 1; k <= K; k++) { for (int i = 0; i < N; i++) { dp[k][i] = max(0ll, a[i]); if (i) dp[k][i] = max({dp[k][i], dp[k][i-1] + a[i], mx[k-1][i-1] + a[i]}); mx[k][i] = dp[k][i]; if (i) mx[k][i] = max(mx[k][i-1], dp[k][i]); cerr << mx[k][i] << ' '; } cerr << '\n'; } cout << dp[K][N-1] << '\n'; return 0; }
#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...