Submission #949959

#	Time	Username	Problem	Language	Result	Execution time	Memory
949959		irmuun	Split the sequence (APIO14_sequence)	C++17	100 / 100	304 ms	83792 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int n,k;
int bef[205][100005];
ll a[100005],pre[100005],dp[2][100005],q[100005],l=1,r=1;
bool case1(int x, int y, int i) {
	return (dp[0][y] - dp[0][x] >= (pre[y] - pre[x]) * (pre[n] - pre[i]));
}

bool case2(int x, int y, int i) {
	return ((dp[0][y] - dp[0][x]) * (pre[i] - pre[y]) <=
	        (dp[0][i] - dp[0][y]) * (pre[y] - pre[x]));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    pre[0]=0;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    fill(dp[0],dp[0]+n+5,0);
    for(ll j=1;j<=k;j++){
        q[r]=0;
        r++;
        for(ll i=1;i<=n;i++){
            while(r-l>1&&case1(q[l],q[l+1],i)){
                l++;
            }
            ll x=q[l];
            dp[1][i]=dp[0][x]+(pre[i]-pre[x])*(pre[n]-pre[i]);
			bef[j][i]=x;
			while(r-l>1&&case2(q[r-2],q[r-1],i)){
			    r--;
			}
			q[r++]=i;
        }
        l=1;
        r=1;
        for(ll i=1;i<=n;i++){
            dp[0][i]=dp[1][i];
        }
    }
    ll mx=-1,ind=-1;
    for(ll i=1;i<=n;i++){
        if(dp[0][i]>mx){
            mx=dp[0][i];
            ind=i;
        }
    }
    cout<<mx<<"\n";
    for(ll i=0;i<k;i++){
        cout<<ind<<' ';
        ind=bef[k-i][ind];
    }
}

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