Submission #539032

#TimeUsernameProblemLanguageResultExecution timeMemory
539032_karan_gandhiFeast (NOI19_feast)C++17
51 / 100
1063 ms25940 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() #define endl '\n' #define pl(var) " [" << #var << ": " << (var) << "] " #define ll long long void solve() { // dp[i][j] = the max sum that can be obtained if j subsegments are chosen and last subsegment ends at i // dp[i][j] = dp[0..i][j-1] int n, k; cin >> n >> k; vector<ll int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } bool good = 1; bool one = 0; for (int i = 0; i < n; i++) { if (arr[i] < 0 && !one) { good = 0; one = 1; } else if (arr[i] < 0 && one) { one = 0; break; } } if (good) { ll int cur = 0; for (int i = 0; i < n; i++) { cur += arr[i]; } cout << cur << endl; return; } if (one) { // depends on the value of k; ll int start = 0; ll int end = 0; ll int all = 0; bool instart = 1; for (int i = 0; i < n; i++) { all += arr[i]; if (arr[i] < 0) { instart = 0; continue; } if (instart) { start += arr[i]; } else { end += arr[i]; } } if (k == 1) { cout << max({start, end, all}) << endl; } else { cout << start + end << endl; } return; } vector<vector<ll int>> dp(n + 1, vector<ll int>(k + 1, 0)); ll int ans = 0; ll int mn = 0; ll int pref = 0; for (int i = 0; i < n; i++) { pref += arr[i]; mn = min(pref, mn); dp[i][1] = max(pref - mn, pref); ans = max(ans, dp[i][1]); if (arr[i] < 0) good = 0; } for (int i = 2; i <= k; i++) { for (int j = i - 1; j < n; j++) { ll int cur = arr[j]; ll int best = arr[j]; for (int k = j - 1; k >= 0; k--) { dp[j][i] = max(dp[k][i - 1] + best, dp[j][i]); cur += arr[k]; best = max(best, cur); } ans = max(ans, dp[j][i]); } } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) 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...