Codeforces Round #585 DIV2 E問題 - Marbles

Source

Codeforces Round #585 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190914-1)のコード

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: 2021年09月27日21時19分41秒
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)

ログイン: