Submission #515919

#	Time	Username	Problem	Language	Result	Execution time	Memory
515919		jk410	Split the sequence (APIO14_sequence)	C++17	28 / 100	2062 ms	2636 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=9e18;
int N,K;
int Prev[201][1001];
ll A[1001],DP[201][1001];
stack<int> S;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    for (int i=1; i<=N; i++){
        cin>>A[i];
        A[i]+=A[i-1];
    }
    for (int t=1; t<=K; t++){
        for (int i=1; i<=N; i++){
            for (int j=1; j<=i; j++){
                if (DP[t][i]<DP[t-1][j]+(A[i]-A[j])*A[j]){
                    DP[t][i]=DP[t-1][j]+(A[i]-A[j])*A[j];
                    Prev[t][i]=j;
                }
            }
        }
    }
    cout<<DP[K][N]<<"\n";
    for (int t=K,i=N; t; t--){
        if (!Prev[t][i])
            break;
        if (Prev[t][i]!=i)
            S.push(Prev[t][i]);
        i=Prev[t][i];
    }
    while (!S.empty()){
        cout<<S.top()<<" ";
        S.pop();
    }
    return 0;
}

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