Submission #1046652

#TimeUsernameProblemLanguageResultExecution timeMemory
1046652vaneaSplit the sequence (APIO14_sequence)C++14
0 / 100
46 ms3164 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll NINF = -1e18; 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+2); for(int i = 1; i <= n; i++) { pref[i] = pref[i-1]+v[i]; } ll ans = 0; vector<int> arr, last(n+1), nxt(n+1, n); vector<bool> vis(n+1); for(int x = 1; x <= k; x++) { ll mx = NINF, pos = -1; for(int i = 1; i <= n; i++) { if(vis[i]) continue; ll left = pref[i]-pref[last[i]]; ll right = pref[nxt[i]]-pref[i]; ll curr = left*right; if(curr > mx) { pos = i; mx = curr; } } vis[pos] = true; arr.push_back(pos); ans += mx; for(int i = 1; i <= n; i++) { if(last[i] < pos && i >= pos) last[i] = pos; if(nxt[i] > pos && i <= pos) nxt[i] = pos; } } 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...