結果
問題 | 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;}