제출 #48638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48638		faishol27	수열 (APIO14_sequence)	C++14	50 / 100	145 ms	5764 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;
ll data[MAXN], pref[MAXN], suff[MAXN];
ll dp[MAXK][MAXN], ans=0;
int tambah[MAXK][MAXN];
stack<int>putus;

void init(){
    memset(data, 0, MAXN);
    memset(pref, 0, MAXN);
    memset(suff, 0, MAXN);
    memset(dp, -1, sizeof dp);
    memset(tambah, -1, sizeof tambah);

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

int main(){
    init();

    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 j=1;j<N;j++){
        ll tmp = pref[j]*suff[j+1];
        //cout << j << " " << tmp << endl;    
        if(dp[1][j] <= tmp){
            dp[1][j] = tmp;
            tambah[1][j] = 0;
        }
    }

    for(int i=2; i<=K; i++){
        for(int j=1;j<N;j++){
            if(j < i) continue;
        
            for(int l=0;l<j;l++){
                ll 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]);
    
    int nxt,
        cnt = K;
    for(int i=N-1;i>0;i--){
        if(ans == dp[cnt][i]){
            putus.push(i);
            nxt = tambah[cnt][i];
            cnt--;
            break;
        }
    }
    while(nxt != 0){
        putus.push(nxt);
        nxt = tambah[cnt][nxt];
        cnt--;
    }
/*
    for(int i=1;i<=K;i++){
        for(int j=1;j<N;j++) cout << tambah[i][j] << " ";
        cout << endl;
    }
*/
    cout << ans << endl;
    
    cout << putus.top();
    putus.pop();
    while(!putus.empty()){
        cout << " " << putus.top();
        putus.pop();
    }
    cout << endl;
 
}

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