Submission #795614

#TimeUsernameProblemLanguageResultExecution timeMemory
795614winthemcut3Split the sequence (APIO14_sequence)C++14
33 / 100
13 ms3156 KiB
#include <bits/stdc++.h> #define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ll long long #define PB push_back #define ALL(v) (v).begin(), (v).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define fi first #define se second #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; /** END OF TEMPLATE **/ const int mxN = 1e5 + 5; int n, k; ll a[mxN]; struct line { ll a, b; int id; line() = default; line(ll a_, ll b_, int id_) : a(a_), b(b_), id(id_) {} ll f(ll x) { return a*x + b; } }; struct CHTrick { deque<line> Y; int iter; CHTrick() = default; bool invalid(const line &l1, const line &l2, const line &l3) { return (l3.b - l1.b)*(l1.a - l2.a) <= (l2.b - l1.b)*(l1.a - l3.a); } void add(line L) { while(Y.size() >= 2 && invalid(Y[Y.size()-2], Y.back(), L)) Y.pop_back(); Y.push_back(L); } line getMax(ll x) { while(Y.size() >= 2 && Y[0].f(x) <= Y[1].f(x)) { Y.pop_front(); } return Y.front(); } void Clear() { while(Y.size()) Y.pop_back(); } }; ll dp[mxN]; int trace[mxN][205]; int main() { FastIO; //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); cin >> n >> k; FOR(i, 1, n) cin >> a[i], a[i] += a[i-1]; CHTrick CH; CH.iter = 0; FOR(i, 1, k) { CH.Clear(); CH.add(line(0, 0, 0)); FOR(j, 1, n) { ll tmp = dp[j]; line L = CH.getMax(a[j]); dp[j] = L.f(a[j]); trace[i][j] = L.id; CH.add(line(a[j], -a[j]*a[j] + tmp, j)); } } cout << dp[n] << '\n'; int id = trace[k][n]; while(k--) { cout << id << ' '; id = trace[k][id]; } return 0; } /* 7 3 4 1 3 4 0 2 3 */
#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...