保存されている過去のバージョンの一覧

2020年09月25日18時16分25秒

Codeforces Round #672 DIV2 E問題 - Battle Lemmings

Source

Codeforces Round #672 DIV2 E問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20200920-1）のコード

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月27日11時00分49秒
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)

ログイン：