結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
|
提出日時 | 2020-09-12 23:19:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 1,767 ms |
コンパイル使用メモリ | 161,460 KB |
実行使用メモリ | 11,148 KB |
最終ジャッジ日時 | 2025-01-02 15:00:51 |
合計ジャッジ時間 | 2,679 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
// No.269 見栄っ張りの募金活動 #include <bits/stdc++.h> using namespace std; typedef long long ll; // const int INF = 2147483647; // const ll INF = 9223372036854775807; const ll MOD = 1e9 + 7; int dp[101][20001]; int main() { int N, S, K; cin >> N >> S >> K; for (int j=0; j<=S; j++) { if (j % N == 0) { dp[1][j] = 1; } } for (int i=2; i<=N; i++) { for (int j=0; j<=S; j++) { if (j - K*(N-i+1) < 0) continue; if (j - (N-i+1) < 0) { dp[i][j] = dp[i-1][j - K*(N-i+1)]; } else { dp[i][j] = (dp[i-1][j - K*(N-i+1)] + dp[i][j - (N-i+1)]) % MOD; } } } cout << dp[N][S] << endl; // **** debug **** /* for (int i=1; i<=N; i++) { cout << "i=" << i << " "; for (int j=0; j<=S; j++) { cout << dp[i][j] << " "; } cout << endl; } */ return 0; }