Submission #934319

#	Time	Username	Problem	Language	Result	Execution time	Memory
934319		Darren0724	Split the sequence (APIO14_sequence)	C++17	0 / 100	2033 ms	16220 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
const int INF=1e18;
const int mod=1e9+9;

int32_t main() {
    LCBorz;
    int n,k;cin>>n>>k;
    vector<int> v(n+1),pre(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        pre[i]=pre[i-1]+v[i];
    }
    vector dp(k+1,vector(n+1,0));
    vector tran(k+1,vector(n+1,0));
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            for(int p=0;p<j;p++){
                int cost=dp[i-1][p]+(pre[n]-pre[j])*(pre[j]-pre[p]);
                if(cost>dp[i][j]){
                    dp[i][j]=cost;
                    tran[i][j]=p;
                }
            }
        }
    }
    int now=0;
    for(int i=1;i<n;i++){
        if(dp[k][i]>=dp[k][now])now=i;
    }
    cout<<dp[k][now]<<endl;
    for(int i=k;i>0;i--){
        cout<<now<<' ';
        now=tran[i][now];
    }
    cout<<endl;


    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