結果
問題 |
No.269 見栄っ張りの募金活動
|
ユーザー |
|
提出日時 | 2020-04-28 00:48:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 1,446 bytes |
コンパイル時間 | 891 ms |
コンパイル使用メモリ | 91,288 KB |
実行使用メモリ | 19,232 KB |
最終ジャッジ日時 | 2024-11-22 17:46:45 |
合計ジャッジ時間 | 1,909 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<iostream> #include<string> #include<cstring> #include <cstdio> #include<utility> #include<algorithm> #include<vector> #include<cmath> #include<map> #include<bitset> #include<queue> #include<stack> #include<set> #include <limits> #include <climits> #include <numeric> #include <cassert> #include <algorithm> #include <functional> using namespace std; typedef long long ll; typedef vector<int>VI; typedef pair<int,int>P; typedef pair<double,double>P_D; //const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; #define PI 3.1415926535897932384626433832795 #define rep(i, n) for (ll i = 0; i < (ll)n; i++) #define reprev(i, n) for (ll i = (ll)n - 1; i >= 0; i--) #define ALL(a) (a).begin(),(a).end() #define C_MAX(a, b) ((a)>(b)?(a):(b)) #define fi first #define se second #define MAX 100100//5 #define MAX_N 200100 #define MAX_B 1001001//6 #define MAX_S 10010010//7 #define SENTINEL 2000000000//9 #define NIL -1 #define MOD 1000000007 #define INF 1 << 29 #define INFTY 1000000000000000000LL #define MAX_INT INT_MAX ll dp[20001][101];//dp[i][j]:=i個のj分割 int main(){ ll n,s,k;cin>>n>>s>>k; ll sub=0; for(int i=0;i<n;i++){ sub+=i*k; } s-=sub; if(s<0){cout<<0<<endl;return 0;} dp[0][0]=1; for(int i=0;i<=s;i++) for(int j=1;j<=n;j++){ if(i-j>=0)dp[i][j]=(dp[i-j][j]+dp[i][j-1])%MOD; else dp[i][j]=dp[i][j-1]%MOD; } ll ans=dp[s][n]; cout<<ans<<endl; }