結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
|
提出日時 | 2025-02-22 10:48:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 720 bytes |
コンパイル時間 | 1,934 ms |
コンパイル使用メモリ | 170,148 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2025-02-22 10:48:26 |
合計ジャッジ時間 | 3,577 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF 1e9+7 int mod(int a, int b){ int r = a % b; return (r>0) ? r : r + b; } int main(){ int N,S,K; vector<vector<int>> dp; cin >> N >> S >> K; for(int i=0; i<N; i++){ S -= i*K; } if(S<0){ cout << 0 << endl; return 0; } dp.resize(N+1,vector<int>(S+1,0)); dp.at(0).at(0) = 1; for(int i=0; i<N; i++){ for(int j=0; j<=S; j++){ if(j-N+i>=0) dp.at(i+1).at(j) = dp.at(i).at(j) + dp.at(i+1).at(j-N+i); else dp.at(i+1).at(j) = dp.at(i).at(j); dp.at(i+1).at(j) = mod(dp.at(i+1).at(j), INF); } } cout << dp.at(N).at(S) << endl; return 0; }