Submission #252974

#TimeUsernameProblemLanguageResultExecution timeMemory
252974LifeHappen__Split the sequence (APIO14_sequence)C++14
100 / 100
980 ms85692 KiB
#include <bits/stdc++.h> using namespace std; #define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a) #define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a) #define forv(a, b) for(auto &a : b) #define rep(i, n) forinc(i, 1, n) #define repv(i, n) forinc(i, 0, n - 1) #define ii pair<int,int> #define fi first #define se second #define all(a) begin(a), end(a) #define reset(f, x) memset(f, x, sizeof(f)) #define eb emplace_back #define pb push_back const int N=1e5+5; long long n,a[N]; long long f[2][N]; int k; int pre[202][N]; int top; long long s[N],x[N]; struct line{long long x,y;int id;} li[N]; double q[N]; double G(line x,line y){return 1.0*(x.y-y.y)/(y.x-x.x);} bool ok(line p){ if(p.x==li[top].x) return false; if(top==1) return 1; double x1=G(p,li[top]); double x2=G(p,li[top-1]); return x1>x2; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin); cin>>n>>k; forinc(i,1,n) cin>>a[i], s[i]=s[i-1]+a[i]; fordec(i,n,1) x[i]=x[i+1]+a[i]; forinc(i,1,k){ int u=i&1; top=0; li[++top]={s[i-1],f[u^1][i-1],i-1}; q[top]=-1e15; forinc(j,i,n-1){ int l=1, r=top, z=0; while(l<=r) { int mid=l+(r-l)/2; if(q[mid]<=-x[j+1]) z=mid, l=mid+1; else r=mid-1; } f[u][j]=s[j]*x[j+1]-li[z].x*x[j+1]+li[z].y; pre[i][j]=li[z].id; line uu; uu.x=s[j], uu.y=f[u^1][j], uu.id=j; if(uu.x==li[top].x && uu.y>=li[top].y) continue; while(top && !ok(uu)) top--; li[++top]=uu; if(top>1) q[top]=G(li[top],li[top-1]); } } int now=0; forinc(i,1,n-1) if(f[k&1][now]<=f[k&1][i]) now=i; cout<<f[k&1][now]<<'\n'; vector<int> ans; ans.pb(now); fordec(i,k,2) ans.pb(pre[i][now]), now=pre[i][now]; reverse(all(ans)); forv(v, ans) cout<<v<<' '; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:40:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...