Submission #1304174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304174		brover29	Split the sequence (APIO14_sequence)	C++20	71 / 100	91 ms	196608 KiB

sequence

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1e5+29;
const string br="617283";
ll dp[N][202];
short a[N];
int n,k;
int pref[N];
int opt[N][205];
struct line{
    ll k,b,i;
    ll get(ll x){
        return k*x+b;
    }
}st[N];
ll sz;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k;
    ll K=k;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }ll ans=-1e18;

    for(int x=1;x<=k;x++){
        sz=0;
        ll r=1;

        for(int i=x;i<=n;i++){
            ll b=1ll*-pref[n]*pref[i-1]+dp[i-1][x-1];
            ll k=pref[i-1];
            while(sz>1&&(b-st[sz-1].b)*(st[sz-1].k-st[sz].k)<=(st[sz].b-st[sz-1].b)*(st[sz-1].k-k))sz--;
            sz++;
            st[sz].k=k;
            st[sz].b=b;
            st[sz].i=i-1;
            r=min(r,sz);
            while(r<sz&&st[r].get(pref[i])<st[r+1].get(pref[i]))r++;
            dp[i][x]=st[r].get(pref[i]);
            opt[i][x]=st[r].i;
        //  assert(st[r].i>=x-1);
            dp[i][x]+=1ll*(pref[n]-pref[i])*(pref[i]);
            ans=max(ans,dp[i][x]);
        }
    }

    cout<<ans<<'\n';
    vector<int>v;
    ll m=0;
    for(ll i=k;i<=n;i++){
        if(dp[i][k]==ans){
            m=i;
            break;
        }
    }
    assert(m);
    while(k){
        v.push_back(m);
        m=opt[m][k];
        k--;
    }
    reverse(v.begin(),v.end());
    assert(v.size()==K);
    for(ll i:v){
        assert(i>0);
        cout<<i<<' ';
    }
}
// I am gay

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