結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
|
提出日時 | 2024-04-02 11:30:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 1,542 bytes |
コンパイル時間 | 5,482 ms |
コンパイル使用メモリ | 309,164 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-09-30 23:09:04 |
合計ジャッジ時間 | 6,624 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;#define rep(i,n) for(int i=0;i<(int)n;i++)#define rep1(i,n) for(int i=1;i<=(int)n;i++)using ll = long long;using ull = unsigned long long;using P = pair<int, int>;using Pl = pair<ll, ll>;using vi = vector<int>;using vvi = vector<vi>;using vd = vector<double>;using vs = vector<string>;using vb = vector<bool>;using vvb = vector<vb>;using vl = vector<long long>;using vvl = vector<vl>;#define inf 2147483642//int max#define linf 900000000000000000const double PI = 3.1415926535897932384626433832795028841971;template<typename T>inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T>inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }long long llceil(long long a, long long b) { if (a % b == 0) { return a / b; }return (a / b) + 1; }#define yes cout<<"Yes"<<endl;#define no cout<<"No"<<endl;#define yesno(ans) cout<<(ans?"Yes":"No")<<endl;#define sortu(a) sort(a.begin(),a.end());int main() {//分割DPll n, s, k; cin >> n >> s >> k;ll zub = s - n*(n - 1)/2 * k;//最低何円//これをn分割ll M = 1e9 + 7;if (zub <0) {cout << 0 << endl;return 0;}vvi dp(n+1, vi(zub+1));dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= zub; j++) {if (j - i >= 0) {dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % M;}else {dp[i][j] = dp[i - 1][j];}}}cout << dp[n][zub] << endl;return 0;}