이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 1e5+5, K = 200+2;
int n, k;
ll dp[2][MAXN], prs[MAXN], s = 0;
int par[K][MAXN];
inline ll getsum(int l, int r){ //[,]
ll tmp = prs[r] - (l>0?prs[l-1]:0ll);
return (((tmp-1ll)*tmp)/2ll);
}
void calc(int id, int l, int r, int opl, int opr){ //[l,r)
if(r-l<1) return;
int mid = (l+r)/2;
int op = opl;
for(int i = opl+1; i <= min(mid-1,opr-1); i++) if(dp[1-(id%2)][i]+getsum(i+1,mid)<dp[1-(id%2)][op]+getsum(op+1,mid)) op = i;
dp[id%2][mid] = dp[1-(id%2)][op]+getsum(op+1,mid); par[id][mid] = op;
calc(id, l, mid, opl, op+1);
calc(id, mid+1, r, op, opr);
return;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k; k++;
for(int i = 0; i < n; i++){
cin >> prs[i];
prs[i] = prs[i] + (i==0?0ll:prs[i-1]);
}
for(int i = 0; i < n; i++) dp[0][i] = getsum(0,i); //getsum: [,]
for(int i = 1; i < k; i++) calc(i,i,n,i-1,n);
cout << (getsum(0,n-1)-dp[1-(k%2)][n-1]) << '\n';
int x = k-1, y = n-1;
vector <int> vec;
while(x>0){
y = par[x][y];
vec.push_back(y+1);
x--;
}
while(!vec.empty()){
cout << vec.back() << " ";
vec.pop_back();
}
cout << '\n';
return 0;
}
# | 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... |