結果
問題 | No.269 見栄っ張りの募金活動 |
ユーザー |
|
提出日時 | 2021-06-14 01:23:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,602 ms / 5,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 1,763 ms |
コンパイル使用メモリ | 171,352 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-12-23 16:51:19 |
合計ジャッジ時間 | 18,719 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using vec = vector<ll>; using mat = vector<vec>; using pll = pair<ll,ll>; #define INF (1LL << 60) #define MOD 1000000007 #define PI 3.14159265358979323846 #define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i)) #define FORR(i,v) for(auto (i):v) #define ALL(x) (x).begin(), (x).end() #define PR(x) cout << (x) << endl #define PS(x) cout << (x) << " " #define SZ(x) ((ll)(x).size()) #define MAX(a,b) (((a)>(b))?(a):(b)) #define MIN(a,b) (((a)<(b))?(a):(b)) #define REV(x) reverse(ALL((x))) #define ASC(x) sort(ALL((x))) #define DESC(x) ASC((x)); REV((x)) #define pb push_back #define eb emplace_back int main() { ll N, S, K; cin >> N >> S >> K; ll M = S - N * (N-1) * K / 2; ll ans; if(M < 0) ans = 0; else { mat dp(N+1, vec(M+1, 0)); REP(i,0,N+1) dp[i][0] = 1; REP(i,1,N+1) { REP(j,1,M+1) { REP(k,0,j/(N-i+1)+1) { dp[i][j] = (dp[i][j] + dp[i-1][j-(N-i+1)*k]) % MOD; } } } ans = dp[N][M]; } PR(ans); return 0; } /* */