Submission #539026

#TimeUsernameProblemLanguageResultExecution timeMemory
539026_karan_gandhiFeast (NOI19_feast)C++17
39 / 100
1092 ms262144 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; for (int i = 0; i < n; i++) { if (arr[i] < 0) good = 0; } if (good) { int cur = 0; for (int i = 0; i < n; i++) { cur += arr[i]; } cout << cur << 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...