結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
|
提出日時 | 2024-04-02 11:45:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 5,000 ms |
コード長 | 1,771 bytes |
コンパイル時間 | 5,088 ms |
コンパイル使用メモリ | 311,108 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-09-30 23:09:15 |
合計ジャッジ時間 | 5,485 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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());long long split_num(long long k,long long n,long long M) {if (n < 0 || k < 0) {return 0;}vector<vector<long long>> split_dp(k + 1, vl(n + 1));split_dp[0][0] = 1;for (long long i = 1; i <= k; i++) {for (long long j = 0; j <= n; j++) {if (j-i >= 0) {split_dp[i][j] = (split_dp[i - 1][j] + split_dp[i][j - i]) % M;}else {split_dp[i][j] = (split_dp[i - 1][j]);}}}return split_dp[k][n];}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;}ll ans = split_num(n, zub, M);cout << ans << endl;return 0;}