Codeforces Round #585 DIV2 E問題 (2500pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, A[4d5];
ll cost[20][20];
ll cbit[20][1100000];
ll dp[1100000];
{
int i, j, k, c1, c2;
ll res, t1, t2;
rd(N,(A--)(N));
rep(i,20) rep(j,i+1,20){
c1 = c2 = 0;
t1 = t2 = 0;
rep(k,N){
if(A[k]==i) c1++, t1 += c2;
if(A[k]==j) c2++, t2 += c1;
}
cost[i][j] = t1;
cost[j][i] = t2;
}
rep(j,20){
rep(i,20) cbit[j][1<<i] = cost[i][j];
rep(i,1<<20){
k = BIT_lowest(i);
if(k != i) cbit[j][i] = cbit[j][i^k] + cbit[j][k];
}
}
rep(i,1,1<<20) dp[i] = ll_inf;
rep(i,1<<20) rep(j,20) if(!(i & 1<<j)){
dp[i|(1<<j)] <?= dp[i] + cbit[j][i];
}
wt(dp[(1<<20)-1]);
}
Current time: 2024年03月29日01時28分35秒
Last modified: 2019年09月16日01時49分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF585 CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)