結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
![]() |
提出日時 | 2020-08-17 00:44:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 1,504 bytes |
コンパイル時間 | 1,563 ms |
コンパイル使用メモリ | 172,988 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-10-11 10:46:53 |
合計ジャッジ時間 | 2,464 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;int t = s - k * n * (n - 1) / 2;if (t < 0) {cout << 0 << endl;return 0;}vector<vll> dp(n+1, vll(t+1));dp[0][0] = 1;rep1(i, n) rep(j, t+1) {if (j-i >= 0) dp[i][j] = (dp[i][j-i] + dp[i-1][j]) % mod;else dp[i][j] = dp[i-1][j];}cout << (dp[n][t] % mod) << endl;return 0;}