Submission #517071

#TimeUsernameProblemLanguageResultExecution timeMemory
517071GurbanSplit the sequence (APIO14_sequence)C++17
71 / 100
351 ms131076 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 203; const int maxn=1e5+3; int n,k; ll p[maxn]; pair<ll,int> dp[N][maxn]; struct line { ll m, c; int idx; long long eval(long long x) { return m * x + c; } long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for(int i = 1;i <= n;i++){ int x; cin >> x; p[i] = x + p[i - 1]; } for(int i = 1;i <= k;i++){ deque<line>dq; dq.push_front({p[i],dp[i-1][i].first - p[i] * p[i],i}); for(int j = i + 1;j <= n;j++){ while(dq.size() >= 2 and dq[0].eval(p[j]) <= dq[1].eval(p[j])) dq.pop_front(); dp[i][j].first = dq[0].eval(p[j]); dp[i][j].second = dq[0].idx; line cur = {p[j],dp[i - 1][j].first - p[j] * p[j],j}; while(dq.size() >= 2 and cur.intersectX(dq[(int)dq.size()-2]) <= dq.back().intersectX(dq[(int)dq.size()-2])) dq.pop_back(); dq.push_back(cur); } } cout<<dp[k][n].first<<'\n'; int idx = dp[k][n].second; for(int i = k-1;i >= 0;i--){ cout<<idx<<' '; idx = dp[i][idx].second; } }
#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...