Submission #111123

#TimeUsernameProblemLanguageResultExecution timeMemory
111123aleksamiSplit the sequence (APIO14_sequence)C++14
33 / 100
118 ms2364 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define MAXK 205 typedef long long ll; ll dp[MAXN][MAXK]; ll s[MAXN]; int opt[MAXN][MAXK]; struct lajn { ll k; ll n; int idx; }; ll f(lajn a,ll x) { return a.k*x+a.n; } bool bad(lajn x,lajn y,lajn z) { return 1LL*(x.n - y.n)*(z.k - y.k) >= 1LL*(y.n - z.n)*(y.k - x.k); } lajn prev_back(deque <lajn> q) { lajn x = q.back(); q.pop_back(); lajn y = q.back(); q.push_back(x); return y; } void calc(int idx,int n) { deque <lajn> q; for(int i = idx; i <= n; i++) { while(1) { if(q.size()<=1)break; lajn a=q.front(); q.pop_front(); lajn b=q.front(); if(f(a,s[i])<=f(b,s[i]))continue; q.push_front(a); break; } if(q.size()) { dp[idx][i]=f(q.front(),s[i]); opt[idx][i]=q.front().idx; } lajn a; a.k=s[i]; a.n=-s[i]*s[i]+dp[idx-1][i]; a.idx=i; while(q.size()>1 && bad(prev_back(q),q.back(),a))q.pop_back(); while(q.size() && a.k==q.front().k && a.n>q.front().n)q.pop_back(); q.push_back(a); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,k; cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> s[i]; s[i]+=s[i-1]; } for(int i = 1; i <= k; i++) { calc(i,n); } cout << dp[k][n] << "\n"; vector <int> qqqqq; int now = n; while(k > 0) { qqqqq.push_back(opt[k][now]);//cout << opt[k][now] << " "; now=opt[k][now]; k--; } sort(qqqqq.begin(),qqqqq.end()); for(auto x:qqqqq)cout << x << " "; 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...