Submission #1039320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039320		fimh	Split the sequence (APIO14_sequence)	C++14	49 / 100	101 ms	67156 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define fi first
#define pll pair<long long,long long>
#define se second
#define isz(x) (int)(x).size()
using namespace std;

const long long inf = 1e18;
const int mod = 1e9+7;
const int maxn = 1e4+5;
const int block = 500;

int dp[maxn][2],trace[maxn][maxn],ps[maxn];

void compute(int j,int l,int r,int optl,int optr){
    if (l>r)return;
    int mid=(l+r)>>1;
    pll best={inf,-1};
    for (int i=optl;i<=min(mid,optr);++i){
        int x=ps[mid]-ps[i-1];
        int val=dp[i-1][0]+x*x;
        if (best.fi>val){
            best={val,i};
            trace[mid][j]=i;
        }
    }
    dp[mid][1]=best.fi;
    int opt=best.se;
    compute(j,l,mid-1,optl,opt);
    compute(j,mid+1,r,opt,optr);
}

void test(){
    int n,k; cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>ps[i];
        ps[i]+=ps[i-1];
        dp[i][0]=ps[i]*ps[i];
    }
    for (int j=2;j<=k+1;++j){
        compute(j,1,n,1,n);
        for (int i=1;i<=n;++i)dp[i][0]=dp[i][1];
    }
    int ans=(ps[n]*ps[n]-dp[n][0])/2;
    cout<<ans<<"\n";
    // cout<<trace[4][2]<<" ";
    vector<int> path;
    int i=n,j=k+1;
    while (1){
        path.push_back(trace[i][j]-1);
        i=trace[i][j]-1; --j;
        if (j==1) break;
    }
    for (int i=isz(path)-1;i>=0;--i)cout<<path[i]<<" ";
}   

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    test();
}

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