Submission #515929

#	Time	Username	Problem	Language	Result	Execution time	Memory
515929		jk410	Split the sequence (APIO14_sequence)	C++17	50 / 100	2059 ms	2628 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=t+1; i<=N; i++){
            DP[t][i]=-1;
            for (int j=t; 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--){
        S.push(Prev[t][i]);
        i=Prev[t][i];
    }
    while (!S.empty()){
        cout<<S.top()<<" ";
        S.pop();
    }
    return 0;
}

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