Submission #384061

#TimeUsernameProblemLanguageResultExecution timeMemory
384061Drew_Split the sequence (APIO14_sequence)C++14
100 / 100
1411 ms81516 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #define ll long long #define pb push_back const int MAX = 1e5 + 7; int n; ll pfx[MAX]; ll dp[2][MAX]; int par[201][MAX]; void rc(int k, int l, int r, int optL, int optR) { if (l > r) return; int mid = (l + r) / 2; ll optVal = -1, optIdx = -1; for (int i = optL; i <= mid && i <= optR; ++i) { //segment [i, n], cut at mid ll v = dp[(k+1)&1][i-1] + (pfx[mid] - pfx[i-1]) * (pfx[n] - pfx[mid]); if (v > optVal) { optVal = v; optIdx = i; } } dp[k&1][mid] = optVal; par[k][mid] = optIdx; rc(k, l, mid-1, optL, optIdx); rc(k, mid+1, r, optIdx, optR); } int main() { ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int k; cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> pfx[i], pfx[i] += pfx[i-1]; for (int i = 1; i <= n; ++i) dp[0][i] = 0; for (int i = 1; i <= k; ++i) rc(i, i, n, i, n); ll res = -1, idx = -1; for (int i = 1; i <= n; ++i) { if (res < dp[k&1][i]) res = dp[k&1][i], idx = i; } vector<int> cut; cut.pb(idx); for (int j = k; j >= 2; --j) cut.pb(idx = par[j][idx] - 1); cout << res << '\n'; for (int i = k-1; i >= 0; --i) { cout << cut[i]; if (i) cout << " "; } cout << '\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...