結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
![]() |
提出日時 | 2020-08-17 07:01:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 1,441 bytes |
コンパイル時間 | 1,613 ms |
コンパイル使用メモリ | 172,468 KB |
実行使用メモリ | 19,456 KB |
最終ジャッジ日時 | 2024-10-11 10:49:22 |
合計ジャッジ時間 | 2,625 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long mod = 1e9 + 7;using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;#define ull unsigned long long#define ld long double#define vi vector<int>#define vll vector<ll>#define vc vector<char>#define vs vector<string>#define vpii vector<pii>#define vpll vector<pll>#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)#define sz(x) ((int)(x).size())#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define SORT(v, n) sort(v, v + n);#define VSORT(v) sort(v.begin(), v.end());#define RSORT(x) sort(rall(x));#define pb push_back#define mp make_pair#define INF (1e18)#define PI (acos(-1))#define EPS (1e-7)ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }int main(){int n, s, k;cin >> n >> s >> k;vector<vll> dp(n+1, vll(s+1));dp[0][0] = 1;rep(i, n) rep(j, s+1) {if (j-(n-i) >= 0) dp[i][j] = (dp[i][j] + dp[i][j-(n-i)]) % mod;if (i-1>=0&&j-k*(n-i)>=0) dp[i][j] = (dp[i][j] + dp[i-1][j-k*(n-i)]) % mod;}cout << dp[n-1][s] << endl;return 0;}