結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
|
提出日時 | 2020-09-13 16:37:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 5,000 ms |
コード長 | 1,320 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 98,932 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-06-13 01:37:54 |
合計ジャッジ時間 | 2,121 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<iostream> #include<string> #include<vector> #include<utility> #include<algorithm> #include<map> #include<cstdlib> #include<cmath> #include<numeric> #include<iomanip> #include<functional> #include<cstdlib> #include<queue> #include<deque> #include <iterator> // std::back_inserter const double PI = acos(-1); using namespace std; using ll =long long; #define rep(i,n)for(ll i=0;i<(n);i++) const int mod = 1000000007; const ll inf = 1e18+1; int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; } ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else { return gcd(b, a % b); } } ll lcm(ll a, ll b) { return a * b / gcd(a, b); }; //fixed << setprecision(2) template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //小文字=大文字+32 int main() { ll N,S,K; cin >> N>>S>>K; S -= K*(N - 1) * N / 2; if (S < 0) { cout << 0; return 0; } vector<vector<ll>>dp(N+1,vector<ll>(S+1,0)); dp[0][0] = 1; for(ll i=1;i<N+1;i++){ for (ll j = 0; j < S+1; j++) { if (j - i >= 0) { dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % mod; } else { dp[i][j] = dp[i - 1][j]; } } } cout << dp[N][S]; }