Codeforces #302 Div1 A, Div2 C: Writing Code

CF302に参加。Aのみ提出failedで0完。1838 → 1770 (-68)。
前回のSRMといい今回のCFといい0完はつらい。

問題

n人のプログラマがいてプログラマiはコード1行に必ずa_i個のバグを仕込む。このn人で合計m行のプログラムを書きたいがバグの総数をb個以下に抑えたい。コーディングの分担としてありうる組み合わせは何通りあるか答えよ。

解法

DPで解ける。
dp[0行目まで書いた][0個のバグ] = 1 として
dp[j行目まで書いた][k個のバグ] += dp[j - 1行目まで書いた][k - a_i個のバグ]
という計算をループを回して各プログラマごとに計算していけばいい。
バグの総数がb個を超えないのなら1人のプログラマが書ける行数に制限はないからこれで正しい組み合わせの数が得られる。最後にm行目書いたときの場合の数の総和を出力すればよい。

#include <iostream>
#define REP(i,a,b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;

int n, m, b, mod;
int a[501], dp[510][510];

int main(void){
    cin >> n >> m >> b >> mod;
    rep(i, n) cin >> a[i];

    dp[0][0] = 1;
    
    rep(i, n)
        REP(j, 1, m + 1)
            REP(k, a[i], b + 1)
                dp[j][k] = (dp[j][k] + dp[j - 1][k - a[i]]) % mod;

    int ans = 0;
    rep(i, b + 1) ans = (ans + dp[m][i]) % mod;
    cout << ans << endl;
    
    return 0;
}