AtCoder Grand Contest 049 E問題 - Increment Decrement

Source

AtCoder Grand Contest 049
問題文

問題概要

省略

解法

省略

cLay（version 20201115-1）のコード

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

int N, C, K; ll A[50], B[50][50];

int sz;
ll val[3000];
int cnt[50][2];
Modint dp[51], nx[51], pw[51];

{
  Modint res = 0;
  rd(N,C,K,B(N,K));

  pw[0] = 1;
  rep(i,N) pw[i+1] = pw[i] * K;
  rep(i,N) rep(j,K) res += B[i][j] * pw[N-1];

  val[sz++] = 0;
  rep(i,N) rep(j,K) val[sz++] = B[i][j];
  sortA(sz, val);

  rep(k,1,sz) if(val[k] != val[k-1]){
    rep(i,N) rep(j,2) cnt[i][j] = 0;
    rep(i,N) rep(j,K) cnt[i][ if[B[i][j]<val[k], 0, 1] ]++;
    rep(i,1,C+1) dp[i] = 0;
    dp[0] = 1;
    rep(i,N){
      rep(j,C+1) nx[j] = 0;
      rep(j,C+1){
        nx[max(0,j-1)] += cnt[i][0] * dp[j];
        nx[min(C,j+1)] += cnt[i][1] * dp[j];
        if(j==C) res -= cnt[i][1] * dp[j] * pw[N-i-1] * (val[k] - val[k-1]);
      }
      rep(j,C+1) dp[j] = nx[j];
    }
  }

  wt(res);
}

Current time: 2024年04月24日08時34分04秒
Last modified: 2020年11月15日01時25分04秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC049 AGC_E
トップページに戻る

Logged in as: unknown user (not login)