| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 48582 | faishol27 | 수열 (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}