Submission #113306

#	Time	Username	Problem	Language	Result	Execution time	Memory
113306		Runtime_error_	Split the sequence (APIO14_sequence)	C++14	39 / 100	204 ms	3704 KiB

sequence

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

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

int main(){

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

    for(ll j=1;j<=k;j++)
        for(ll i=1;i<=n;i++)
            for(ll 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(ll i=1;i<=n;i++)
        if(ans<dp[i][k].first)
            ans=dp[i][k].first,idx=i;

    split.push_back(idx);
    for(ll 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: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29