Codeforces Round #584 - Dasha Code Championship - Elimination Round E2問題 - Rotate Columns (hard version)

Source

Codeforces Round #584 - Dasha Code Championship - Elimination Round E2問題 (1500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190914-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int TEST, N, M, A[12][2000];
int dp[4096], nx[4096], mx[2000], ind[4096], s[4096];
{
  int i, j, k, kk, m;
  
  rd(TEST);
  rep(TEST){
    rd(N,M);
    rep(i,N) rep(j,M) rd(A[i][j]);
    rep(j,M){
      ind[j] = j;
      mx[j] = 0;
      rep(i,N) mx[j] >?= A[i][j];
    }
    rsortA(M, mx, ind);

    rep(i,1<<N) dp[i] = 0;
    rep(kk,min(N,M)){
      k = ind[kk];
      rep(i,1<<N){
        s[i] = 0;
        rep(j,N) if(i&1<<j) s[i] += A[j][k];
      }
      rep(m,N){
        rep(i,1<<N){
          j = 2*i;
          if(j >= (1<<N)) j ^= ((1<<N) | 1);
          s[i] >?= s[j];
        }
      }
      rep(i,1<<N) nx[i] = dp[i];
      rep(i,1<<N){
        m = ((1<<N)-1) ^ i;
        for(j=m; j; j = ((j-1)&m)){
          nx[i|j] >?= dp[i] + s[j];
        }
      }
      rep(i,1<<N) dp[i] = nx[i];
    }
    
    wt(nx[(1<<N)-1]);
  }
}

Current time: 2024年04月18日23時10分34秒
Last modified: 2019年09月15日12時53分51秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF584
トップページに戻る

Logged in as: unknown user (not login)