Submission #142519

#TimeUsernameProblemLanguageResultExecution timeMemory
142519meatrowSplit the sequence (APIO14_sequence)C++17
0 / 100
177 ms7300 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //#pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int mod = 1e9 + 7; const int N = 1e5 + 5; const int K = 205; struct Line { ll k, b; int pos; ll eval(ld x) { return k * x + b; } }; inline ld isec(Line &p, Line &q) { return ((ld)p.b - q.b) / (q.k - p.k); } struct CHT { int s; Line l[N]; //int pt; void clr() { s = 0;// pt = 0; } void add(Line a) { while(s >= 2 && isec(l[s - 2], l[s - 1]) >= isec(l[s - 1], a)) s--;//, pt = min(pt, s - 1); l[s++] = a; } pair<ll, int> get(ll x) { int lf = 1, rg = s - 1; if(s == 1 || x <= isec(l[0], l[1])) lf = 0; else while(lf < rg) { int md = (lf + rg + 1) >> 1; if(isec(l[md - 1], l[md]) <= x) lf = md; else rg = md - 1; } return { l[lf].eval(x), l[lf].pos }; } // // ll get(ll x) { // while(pt != s - 1 && isec(l[pt], l[pt + 1]) <= x) pt++; // return l[pt].eval(x); // } }; int a[N]; ll pref[N]; ll dp[K][N]; int way[K][N]; CHT cht; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for (int i = 2; i <= n; i++) { int pos = upper_bound(pref + 1, pref + i + 1, pref[i] / 2) - pref - 1; for (int j = max(1, pos - 5); j <= min(pos + 5, i - 1); j++) { if ((pref[i] - pref[j]) * pref[j] >= dp[1][i]) { dp[1][i] = (pref[i] - pref[j]) * pref[j]; way[1][i] = j; } } } for (int i = 2; i <= k; i++) { cht.clr(); cht.add({ 0, -1, -1 }); for (int j = 1; j <= n; j++) { auto p = cht.get(pref[j]); dp[i][j] = p.first; way[i][j] = p.second; cht.add({ pref[j], dp[i - 1][j] - pref[j] * pref[j], j }); } } cout << dp[k][n] << '\n'; int kek = n; vector<int> ans; for (int i = k; i > 0; i--) { ans.push_back(way[i][kek]); kek = way[i][kek]; } reverse(ans.begin(), ans.end()); for (int i : ans) { cout << i << ' '; } 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...