AtCoder Grand Contest 049 D問題 - Convex Sequence

Source

AtCoder Grand Contest 049
問題文

問題概要

省略

解法

省略

cLay（version 20201115-1）のコード

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

Modint dp[501][1d5+1], sm[502][1d5+1];
{
  int @N, @M, i, j, k, x, y;
  Modint res = 0;

  dp[0][0] = 1;
  rep(i,1,501){
    k = i * (i+1) / 2;
    rep(j,1d5+1){
      dp[i][j] = dp[i-1][j];
      if(j-k >= 0) dp[i][j] += dp[i][j-k];
    }
  }
  rep(i,1,501){
    k = min(1d5+1, i * (i+1) / 2);
    rrep(j,k,1d5+1) dp[i][j] = dp[i][j-k];
    rrep(j,k) dp[i][j] = 0;
  }
  rep(i,501) rep(j,1d5+1) sm[i+1][j] = sm[i][j] + dp[i][j];
  rep(i,502) rep(j,N,1d5+1) sm[i][j] += sm[i][j-N];

  REP(x,min(N,500)){
    y = min(500, N-x-1);
    rep(j,M+1) res += dp[x][j] * sm[y+1][M-j];
  }

  wt(res);
}

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

Logged in as: unknown user (not login)