Submission #111126

#TimeUsernameProblemLanguageResultExecution timeMemory
111126aleksamiSplit the sequence (APIO14_sequence)C++14
0 / 100
48 ms8660 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ll; #define MAXN 100005 #define MAXK 205 const ll INF = 1e18; ll dp[MAXN][MAXK]; ll a[MAXN]; int opt[MAXN][MAXK]; struct lajn { ll k; ll n; int idx; }; ll eval(lajn l,ll x){return l.k*x+l.n;} ll presekx(lajn a,lajn b) { if(a.k==b.k)return INF; return 1.00*(a.n-b.n)/(b.k-a.k); } deque <lajn> q; lajn next_front() { lajn z = q.front(); q.pop_front(); lajn o = q.front(); q.push_front(z); return o; } lajn next_back() { lajn z = q.back(); q.pop_back(); lajn o = q.back(); q.push_back(z); return o; } 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 <= n; i++) { for(int j = 1; j <= k; j++) { dp[j][i]=-INF; } } for(int i = 1; i <= n; i++)dp[0][i]=0LL; for(int i = 1; i <= k; i++) { q.clear(); lajn zzz; zzz.k=0; zzz.n=0; q.push_front(zzz); for(int j = 1; j <= n; j++) { while(q.size()>1 && presekx(q.front(),next_front())<=a[j])q.pop_front(); if(q.size())dp[i][j]=q.front().k*a[j]+q.front().n,opt[i][j]=q.front().idx; lajn now; now.k=a[j]; now.n=-a[j]*a[j]+dp[i-1][j]; while(q.size()>2 && presekx(next_back(),q.front())>=presekx(q.front(),now))q.pop_back(); q.push_back(now); } } 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...