Submission #685216

#	Time	Username	Problem	Language	Result	Execution time	Memory
685216		PoonYaPat	Split the sequence (APIO14_sequence)	C++14	0 / 100	2077 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,ans[100001][201];
ll qs[100001],dp[100001][201];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; ++i) {
        cin>>qs[i];
        qs[i]+=qs[i-1];
    }

    for (int i=1; i<n; ++i) dp[i][1]=qs[i]*(qs[n]-qs[i]);

    for (int j=2; j<=k+1; ++j) {
        for (int i=1; i<=n; ++i) {

            for (int l=1; l<i; ++l) {

                if (dp[i][j]<dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i])) {
                    ans[i][j]=l;
                    dp[i][j]=dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i]);
                }
            }

        }
    }
/*
    for (int j=1; j<=k+1; ++j) {
        for (int i=1; i<=n; ++i) cout<<dp[i][j]<<" ";
        cout<<"\n";
    } */

    cout<<dp[n][k+1]<<"\n";


    vector<int> v;
    while (k) {
        v.push_back(ans[n][k+1]);
        n=ans[n][k];
        --k;
    }
    reverse(v.begin(),v.end());

    for (auto s : v) cout<<s<<" ";

}

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