Submission #1039328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039328		fimh	Split the sequence (APIO14_sequence)	C++14	0 / 100	20 ms	50524 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;
using ll=long long;

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

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

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];
        ll val=dp[i-1][0]+1ll*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];
    }
    ll ans=(1ll*ps[n]*ps[n]-dp[n][0])>>1;
    cout<<ans<<"\n";
    vector<int> path;
    int y=k+1,x=trace[n][y];
    while (y>1){
        path.push_back(x-1);
        x=trace[x-1][y]; --y;
    }
    reverse(path.begin(),path.end());
    for (int i : path) cout<<i<<" ";
}

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

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