Submission #48629

#	Time	Username	Problem	Language	Result	Execution time	Memory
48629		faishol27	Split the sequence (APIO14_sequence)	C++14	0 / 100	3 ms	2172 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;
 
int N, K;
int data[MAXN], pref[MAXN], suff[MAXN];
pi dp[MAXN][205]; //{ind putus, score}
int ans = 0;
stack<int> putus;
 
pi MAX(pi a, pi b){
    if(a.se != b.se){
        if(a.se > b.se) return a;
        else return b;
    }else{
        if(a.fi > b.fi) return a;
        else return b;
    }
}
 
void cariPemutusan(){
    int nxt,
        tK = K-1;

    for(int i=N-1;i>0;i--){
        if(dp[i][K].se == ans){
            putus.push(i);
            nxt = dp[i][K].fi;
            break;
        }
    }

    while(nxt != 0){
        putus.push(nxt);
        nxt = dp[nxt][tK].fi;
        tK--;
    }
}
 
int main(){
    memset(data, 0, MAXN);
    memset(pref, 0, MAXN);
    memset(suff, 0, MAXN);
    memset(dp, 0, sizeof dp);
    
    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<=N-1;i++){
        for(int j=1;j<=K;j++){
            for(int l=0;l<i;l++){
                if(l >= j) break;

                pl  tmp,
                    bef = dp[l][j-1];
                
                tmp.fi = l;
                tmp.se = bef.se + (pref[i]-pref[l])*suff[i+1];
 
                dp[i][j] = MAX(dp[i][j], tmp);
            }
        }
    }
/*    
    for(int i=1;i<=N-1;i++){
        for(int j=1;j<=K;j++){
            if(j > i) break;
            
            cout << "[" << dp[i][j].fi << ", " << dp[i][j].se << "] ";
        }
        cout << endl;
    }
*/
    for(int i=1;i<=N;i++) ans = max(ans, dp[i][K].se);
    
    cariPemutusan();

    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