Submission #113302

#	Time	Username	Problem	Language	Result	Execution time	Memory
113302		Runtime_error_	Split the sequence (APIO14_sequence)	C++14	0 / 100	7 ms	2008 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int inf=1e3+9,K=209;
int n,k,ans,idx;
int pre[inf],a[inf];
pair<int,int> dp[inf][K];
vector<int> split;

int sum(int x,int y){
    return pre[y]-pre[x];
}

int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],pre[i]=pre[i-1]+a[i];

    for(int j=1;j<=k;j++)
        for(int i=1;i<=n;i++)
            for(int z=0;z<i;z++)
                dp[i][j]=max(dp[i][j],make_pair(dp[z][j-1].first+sum(z,i)*sum(i,n),z));

    for(int j=1;j<=k;j++){
        for(int i=1;i<=n;i++)
            cout<<dp[i][j].first<<" "<<dp[i][j].second<<"   ";
        cout<<endl;
    }

    for(int i=1;i<=n;i++)
        if(ans<dp[i][k].first)
            ans=dp[i][k].first,idx=i;

    split.push_back(idx);
    for(int j=k;j>1;j--)
        idx=dp[idx][j].second,split.push_back(idx);
    reverse(split.begin(),split.end());

    cout<<ans<<endl;
    for(auto o:split)
        cout<<o<<" ";
    cout<<endl;
}

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