제출 #48585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48585		faishol27	수열 (APIO14_sequence)	C++14	0 / 100	526 ms	4932 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, tambah[MAXN][205];
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 pos, ll score, int str){
    if(pos == 0) return;

    for(int i=str-1;i>0;i--){
        if(dp[i][pos].se == score){
            putus.push(i);
            cariPemutusan(pos-1, score-tambah[i][pos], i);
            break;
        }
    }
}

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

    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++){
                pl  tmp,
                    bef = dp[l][j-1];
                tmp.fi = i;
                tmp.se = bef.se + (pref[i]-pref[bef.fi])*suff[i+1];

                dp[i][j] = MAX(dp[i][j], tmp);

                if(dp[i][j].se == tmp.se){
                    tambah[i][j] = (pref[i]-pref[bef.fi])*suff[i+1];
                }
            }
        }
    }
/*    
    for(int i=1;i<=N-1;i++){
        cout << tambah[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);
    cout << ans << endl;

    cariPemutusan(K, ans, N-1);

    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