EDPC「M - Candies」🍬imos

  • Quiz
  • AC
  • 解説
    • 累積和を使っている解法が多かったのですが、imosで解けたので書いておく
    • dpテーブルの定義は dp[i][j] : i個目まで見て、j個配ったときの場合の数
    • 愚直に実装するとTLEする（下記コードの「これではTLEする」の部分）
    • 「同じ値を範囲に足している」ので、imosに書き換えることができる

f:id:peroon:20210309201825p:plain

mint dp[110][200010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K;
    cin>>N>>K;

    VI A(N);
    rep(i, N) cin >> A[i];

    dp[0][0]=1;

    rep(i,N){
      // 今回はa個まで配れる
      ll a = A[i];

      // 今j個消費した状態から
      rep(j,K+1){

        // これではTLEする
        // rep(k,a+1){
        //   // k個配布する
        //   if(j+k>K)break;
        //   dp[i+1][j+k] += dp[i][j];
        // }

        // imos
        dp[i+1][j+0] += dp[i][j];
        dp[i+1][j+a+1] -= dp[i][j];
      }

      // imos
      rep(j,K+1){
        dp[i+1][j+1] += dp[i+1][j];
      }
    }

    ll ans = dp[N][K].x;
    p(ans);
    
    return 0;
}