Submission #111335

#TimeUsernameProblemLanguageResultExecution timeMemory
111335aleksamiSplit the sequence (APIO14_sequence)C++14
71 / 100
909 ms132096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 100005 #define MAXK 205 const ll INF = 1e18; struct line {ll n;ll k;int id;}; double presekx(line a,line b) { if(a.k==b.k)return INF; return (a.n-b.n)/(b.k-a.k); } ll dp[MAXK][MAXN]; ll a[MAXN]; int opt[MAXK][MAXN]; deque <line> q; line next_front() { line a = q.front(); q.pop_front(); line b = q.front(); q.push_front(a); return b; } line prev_back() { line a = q.back(); q.pop_back(); line b = q.back(); q.push_back(a); return b; } ll eval(line l,ll x) { return l.k*x+l.n; } int main() { ios_base::sync_with_stdio(false); int n,k; cin >> n >> k; for(int i = 1; i <= n; i++)cin >> a[i],a[i]+=a[i-1]; for(int i = 1; i <= k; i++) { q.clear(); for(int j = i; j <= n; j++) { while(1) { if(q.size()<=1)break; if(eval(q.front(),a[j])<=eval(next_front(),a[j])){q.pop_front();continue;} break; } if(q.size()) { dp[i][j]=eval(q.front(),a[j]); opt[i][j]=q.front().id; } line add; add.k=a[j]; add.n=-a[j]*a[j]+dp[i-1][j]; add.id=j; while(1) { if(q.size()<=1)break; if(q.back().k==add.k){q.pop_back();continue;} if(q.back().k==prev_back().k){q.pop_back();continue;} if(presekx(prev_back(),q.back())>=presekx(q.back(),add)){q.pop_back();continue;} break; } q.push_back(add); } } cout << dp[k][n] << "\n"; int now = n; while(k > 0) { cout << opt[k][now] << " "; now=opt[k][now]; k--; } 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...