이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
using namespace std;
#define mid(l, u) ((l+u)/2)
//#define cin fin
//#define cout fout
const int N = 100005;
const int K = 205;
int a[N];
int pref[N], suff[N];
int n, k;
int dp[N][K];
int nxt[N][K];
bool vis[N][K];
int f(int i, int j){
if(i>n && j!=0) return -INF;
if(j==0){
nxt[i][j] = -1;
return 0;
}
if(vis[i][j]) return dp[i][j];
vis[i][j] = true;
int amt = (suff[i]/(j+1));
int l = i;
int u = n - (j+1);
int pt = i;
while(l<=u){
int m = mid(l, u);
int qt = pref[m] - pref[i-1];
if(qt <= amt){
pt = max(pt, m);
l = m+1;
}
else{
u = m-1;
}
}
//try pt
int ans1 = f(pt+1, j-1) + ((pref[pt] - pref[i-1])*(suff[pt+1]));
//try pt+1
int ans2 = 0;
if(pt+1 <= (n - (j+1))) ans2 = f(pt+2, j-1) + ((pref[pt+1] - pref[i-1])*(suff[pt+2]));
//cout<<i<<" "<<j<<" ";
if(ans1 > ans2){
nxt[i][j] = pt;
}
else{
nxt[i][j] = pt+1;
}
//cout<<nxt[i][j]<<endl;
return dp[i][j] = max(ans1, ans2);
}
signed main(){
//ofstream fin("2.in");
//ofstream fout("2.out");
cin>>n>>k;
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++) pref[i] = pref[i-1] + a[i];
for(int i = n;i>=1;i--) suff[i] = suff[i+1] + a[i];
cout<<f(1, k)<<endl;
int nextind = 1;
int currk = k;
int lol = 0;
while(lol<10 && nxt[nextind][currk]>0){
cout<<nxt[nextind][currk]<<" ";
nextind = nxt[nextind][currk] + 1;
currk--;
lol++;
}
}
/*
7 3
4 1 3 4 0 2 3
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |