Submission #32215

#	Time	Username	Problem	Language	Result	Execution time	Memory
32215		dongwon0427	Split the sequence (APIO14_sequence)	C++98	100 / 100	783 ms	86164 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;

int n,k;
ll A[100005];
ll dp1[100005];
ll dp2[100005];
ll sum[100005];
struct line {
    ll tan,y;
    int idx;
};
line L[100005];
int sz,p;
inline ld inter(line a,line b) {
    if(a.tan==b.tan) {
        return -1000000000000000000ll;
    }
    return (ld)(a.y-b.y)/(ld)(b.tan-a.tan);
}
inline void linepush(ll tan,ll y,int idx) {
    line s;
    s.tan=tan; s.y=y; s.idx=idx;
    while(sz>=2 && inter(L[sz-1],s) < inter(L[sz-2],L[sz-1]) ) {
        sz--;
        if(p>=sz) p--;
    }
    L[sz++]=s;
}
int via[201][100005];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+A[i];
    for(int i=1;i<=n;i++) {
        dp1[i]=sum[i]*(sum[n]-sum[i]);
    }
    for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)via[i][j]=-1;
    for(int i1=2;i1<=k;i1++) {
        sz=0,p=-1;
        linepush(sum[i1-1],dp1[i1-1]-sum[n]*sum[i1-1],i1-1);
        for(int i=i1;i<=n;i++) {
            while(p<sz-1 && inter(L[p],L[p+1]) <= sum[i]) p++;
            dp2[i] = L[p].tan*sum[i] + L[p].y + sum[i]*sum[n] - sum[i]*sum[i];
            via[i1][i]=L[p].idx;
            linepush(sum[i], dp1[i]-sum[n]*sum[i], i);
        }
        for(int i=1;i<=n;i++) {
            dp1[i]=dp2[i];
            dp2[i]=0;
        }
    }
    ll _max = 0; int maxidx=1;
    for(int i=1;i<=n;i++) {
        if(_max < dp1[i]) {
            _max = dp1[i];
            maxidx= i;
        }
    }
    vector<int> v;
    for(int i=k;i>=1;i--) {
        v.push_back(maxidx);
        maxidx=via[i][maxidx];
    }
    reverse(v.begin(),v.end());
    cout<<_max<<"\n";
    for(int i=0;i<v.size();i++) {
        cout<<v[i]<<' ';
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                  ^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29