Codeforces Round #672 DIV2 E問題 (3000pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, A[80];
int sz, ps, pl[80];
int dp[3200][81], nx[3200][81];
int cost[81][81][81];
int res[3200];
{
int i, j, k, m, x, y, z;
rd(N,A(N));
sz = arrCountVal(N,A,1)+1;
k = 0;
rep(i,N){
if(A[i]==1) k++;
if(A[i]==0) pl[ps++] = k;
}
m = N * (N-1) / 2;
rep(i,m+1) rep(j,ps+1) dp[i][j] = int_inf;
rep(i,m+1) dp[i][0] = 0;
rep(k,sz) rep(j,ps+1){
cost[k][j][j] = 0;
rep(x,j+1,ps+1) cost[k][j][x] = cost[k][j][x-1] + abs(pl[x-1] - k);
}
rep(k,sz){
rep(i,m+1) rep(j,ps+1) nx[i][j] = int_inf;
rep(i,m+1) rep(j,ps+1) rep(x,j,ps+1){
y = (x-j) * (x-j-1) / 2;
z = cost[k][j][x];
if(i+z <= m) nx[i+z][x] <?= dp[i][j] + y;
}
rep(i,m+1) rep(j,ps+1) dp[i][j] = nx[i][j];
}
rep(i,m+1) res[i] = ps * (ps-1) / 2 - dp[i][ps];
wt(res(m+1));
}
Current time: 2024年04月18日05時00分42秒
Last modified: 2020年09月25日18時16分25秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF672 CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)