Submission #1046627

#TimeUsernameProblemLanguageResultExecution timeMemory
1046627vaneaSplit the sequence (APIO14_sequence)C++14
50 / 100
2041 ms24920 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n, k; cin >> n >> k; vector<ll> v(n+1); for(int i = 1; i <= n; i++) { cin >> v[i]; } vector<ll> pref(n+1), suf(n+2); for(int i = 1; i <= n; i++) { pref[i] = pref[i-1]+v[i]; } for(int i = n; i>=1; i--) { suf[i] = suf[i+1]+v[i]; } vector<vector<ll>> dp(n+1, vector<ll>(k+1)); vector<vector<int>> last(n+1, vector<int>(k+1)); for(int i = 1; i <= n; i++) { for(int j = 0; j < i; j++) { for(int x = 1; x <= min(k, i); x++) { ll f = pref[i]-pref[j]; if(dp[j][x-1] + f*suf[i+1] >= dp[i][x]) { dp[i][x] = dp[j][x-1] + f*suf[i+1]; last[i][x] = j; } } } } ll ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, dp[i][k]); } int idx = 0, x = k; for(int i = 1; i <= n; i++) { if(dp[i][k] == ans) { idx = i; break; } } vector<int> arr; while(x != 0) { arr.push_back(idx); idx = last[idx][x]; --x; } reverse(arr.begin(), arr.end()); cout << ans << '\n'; for(auto it : arr) { cout << it << ' '; } 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...