結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
![]() |
提出日時 | 2021-10-28 22:58:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 5,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 4,236 ms |
コンパイル使用メモリ | 250,600 KB |
最終ジャッジ日時 | 2025-01-25 08:04:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pdd = pair<ld, ld>; using pll = pair<ll, ll>; using pli = pair<ll, int>; using pil = pair<int, ll>; template <typename T> using Graph = vector<vector<T>>; const int MOD = 1e9 + 7; const ld PI = acos(-1); int main() { cin.tie(0); ios::sync_with_stdio(false); int N, S, K; cin >> N >> S >> K; int tmp = N * (N - 1) / 2 * K; if (S < tmp) { cout << 0 << endl; return 0; } S -= tmp; vector<vector<int>> dp(N + 1, vector<int>(S + 1)); dp[0][0] = 1; for (int i = 0; i < N; ++i) { for (int j = 0; j <= S; ++j) { int k = N - i; if (j >= k) { (dp[i][j] += dp[i][j - k]) %= MOD; } (dp[i + 1][j] += dp[i][j]) %= MOD; } } cout << dp[N][S] << endl; return 0; }