| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 48582 | faishol27 | 수열 (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
#define fi first
#define se second
const int MAXN = 1e5+5;
int N, K;
int data[MAXN], pref[MAXN], suff[MAXN];
pl dp[MAXN][205]; //{ind putus, score}
int ans = 0, tambah[MAXN][205];
stack<int> putus;
pl MAX(pl a, pl 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){
if(pos == 0) return;
for(int i=1;i<=N-1;i++){
if(dp[i][pos].se == score){
putus.push(i);
cariPemutusan(pos-1, score-tambah[i][pos]);
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);
cout << putus.top();
putus.pop();
while(!putus.empty()){
cout << " " << putus.top();
putus.pop();
}
cout << endl;
}