Submission #48612

#	Time	Username	Problem	Language	Result	Execution time	Memory
48612		faishol27	Split the sequence (APIO14_sequence)	C++14	0 / 100	118 ms	2248 KiB

sequence

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

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

#define fi first
#define se second

const int MAXN = 1e3+5;
const int MAXK = 205;

// f(x,y) = score
// x = pemotongan ke-x
// y = indeks pemotongan
//
//

int N, K;
int data[MAXN], pref[MAXN], suff[MAXN];
int dp[MAXK][MAXN], ans=0;
int tambah[MAXK][MAXN];
stack<int>putus;

void cariSkenario(int cnt, int str, int score){
    if(cnt == 0) return;

    for(;str>0;str--){
        if(dp[cnt][str] == score){
            putus.push(str);
            cariSkenario(cnt-1, str-1, score-tambah[cnt][str]);
            break;
        }
    }
}

void DFS(int pos){
    if(pos == 1) return;

    putus.push(tambah[pos][putus.top()]);
    DFS(pos-1);
}

int main(){
    memset(data, 0, MAXN);
    memset(pref, 0, MAXN);
    memset(suff, 0, MAXN);
    memset(dp, -1, sizeof dp);

    for(int i=0;i<MAXN;i++) dp[0][i] = 0;
    for(int i=0;i<MAXK;i++) dp[i][0] = 0;

    cin >> N >> K;
    
    for(int i=1;i<=N;i++){
        cin >> data[i];
        pref[i] = data[i]+pref[i-1];
    }

    for(int i=N;i>0;i--){
        suff[i] = suff[i+1]+data[i];
    }

    for(int i=1; i<=K; i++){
        for(int j=1;j<N;j++){
            if(j < i) continue;
        
            for(int l=0;l<j;l++){
                int tmp = dp[i-1][l]+(pref[j]-pref[l])*suff[j+1];
                
                if(dp[i][j] <= tmp){
                    dp[i][j] = tmp;
                    tambah[i][j] = l;
                }
            }
        }
    }
  
    for(int i=1;i<N;i++) ans = max(ans, dp[K][i]);
    for(int i=N-1;i>0;i--){
        if(ans == dp[K][i]){
            putus.push(i);
            break;
        }
    }
    
    DFS(K);

    cout << ans << endl;
    
    cout << putus.top();
    putus.pop();
    while(!putus.empty()){
        cout << " " << putus.top();
        putus.pop();
    }
    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