Submission #241948

#TimeUsernameProblemLanguageResultExecution timeMemory
241948michaoSplit the sequence (APIO14_sequence)C++14
71 / 100
478 ms131076 KiB
#include <bits/stdc++.h> #define ll long long int #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=1e5+1000; ll dp[201][MAX]; int tab[MAX]; int pref[MAX]; ll prefix(int a,int b) { return pref[b]-pref[a-1]; } class CHT { public: deque<pair<int,ll> > D; void add(pair<int,ll> f) { while(true) { if(D.size()<=1) break; pair<int,ll> a=D.back(); D.pop_back(); pair<int,ll> b=D.back(); // (a.nd-f.nd)/(f.st-a.st)<=(b.nd-a.nd)/(a.st-b.st); // (a.nd-f.nd)*(a.st-b.st)<=(b.nd-a.nd)*(f.st-a.st) ll x1=(a.nd-f.nd)*(a.st-b.st); ll x2=(b.nd-a.nd)*(f.st-a.st); if(x1<=x2) continue; else { D.pb(a); break; } } D.pb(f); } ll getmin(int x) { while(D.size()>1) { pair<int,ll> a=D.front(); D.pop_front(); pair<int,ll> b=D.front(); ll p1=(ll)x*a.st+a.nd,p2=(ll)x*b.st+b.nd; if(p2>=p1) continue; else { D.push_front(a); break; } } pair<int,ll> a=D.front(); return (ll)x*a.st+a.nd; } }; vi ans; int32_t main() { BOOST; int n,k; cin>>n>>k; for (int i=1;i<=n;i++)cin>>tab[i]; for (int i=1;i<=n;i++)pref[i]=pref[i-1]+tab[i]; for (int i=1;i<=k;i++) { CHT L; for (int j=2;j<=n;j++) { L.add(mp(pref[j-1],-(ll)pref[j-1]*pref[j-1]+dp[i-1][j-1])); dp[i][j]=L.getmin(pref[j]); } } /* for (int i=1;i<=k;i++) for (int j=1;j<=n;j++) for (int l=j;l>=2;l--) dp[i][j]=max(dp[i][j],prefix(l,j)*prefix(1,l-1)+dp[i-1][l-1]); */ cout<<dp[k][n]<<"\n"; int wsk=n; for (int i=k;i>=1;i--) for (int j=wsk;j>=2;j--) { if (dp[i][wsk]==prefix(j,wsk)*prefix(1,j-1)+dp[i-1][j-1]) { wsk=j-1; ans.pb(j-1); break; } } for (auto it:ans)cout<<it<<" "; 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...