Submission #1150405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150405		cnnuy	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	324 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define m first
#define n second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+3;

typedef pair<ll,ll> ln;
vector<ln> vt;
vector<int> idx;
long double inter(ln a,ln b) {
    assert(a.m!=b.m);
    return (long double)(b.n-a.n)/((long double)(a.m-b.m));
}
bool bad(ln a,ln b,ln c) {
    if (b.m==c.m) return (b.n>c.n);
    return inter(a,c)>=inter(a,b);
}
pair<ll,int> query(ll x) {
    if (sz(vt)==0) return {-1e17,69};
    int l=0,r=sz(vt)-1;
    while(l<r) {
        int mid=l+(r-l+1)/2;
        if (mid==0) l=mid;
        else {
            if (inter(vt[mid],vt[mid-1])>=x) l=mid;
            else r=mid-1;
        }
    }
    return {vt[l].m*x+vt[l].n,idx[l]};
}
void insert(ll x,ll y,int id) {
    if (sz(vt) && vt.back().m==x && vt.back().n>=y) return;
    while(sz(vt)>=2 && bad(vt[sz(vt)-2],vt.back(),{x,y})) vt.pop_back(),idx.pop_back();
    while(sz(vt) && vt.back().m==x) vt.pop_back(),idx.pop_back();
    vt.pb({x,y});
    idx.pb(id);
}
ll dp[202][N],pf[N],ans=0;
int opt[202][N];
int n,k,a[N];
vector<int> track;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    For(i,1,n) {
        cin >> a[i];
        pf[i]=pf[i-1]+a[i];
    }
    pair<int,int> cur={0,0};

    For(j,1,k) {
        vt.clear();
        idx.clear();
        insert(-pf[j-1],dp[j-1][j-1],j-1);
        For(i,j,n-1) {
            auto res=query(pf[n]-pf[i]);
            dp[j][i]=pf[i]*(pf[n]-pf[i])+res.m;
            opt[j][i]=res.n;
            insert(-pf[i],dp[j-1][i],i);
        }
        For(i,1,n-1) 
            if (dp[j][i]>ans) {
                ans=dp[j][i];
                cur={j,i};
            }
    }
    cout << ans << endl;
    while(cur.m>0) {
        track.pb(cur.n);
        cur={cur.m-1,opt[cur.m][cur.n]};
    }
    reverse(all(track));
    for(auto el: track) cout << el << " ";
    return 0;
}

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