結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
|
提出日時 | 2020-03-21 04:57:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,737 bytes |
コンパイル時間 | 1,548 ms |
コンパイル使用メモリ | 173,136 KB |
実行使用メモリ | 483,328 KB |
最終ジャッジ日時 | 2024-07-17 11:57:44 |
合計ジャッジ時間 | 12,243 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 WA * 1 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:25:17: warning: 't_e' may be used uninitialized [-Wmaybe-uninitialized] 25 | ll t_s, t_e; | ^~~ main.cpp:25:12: warning: 't_s' may be used uninitialized [-Wmaybe-uninitialized] 25 | ll t_s, t_e; | ^~~
ソースコード
#include "bits/stdc++.h" using namespace std; typedef long long int ll; typedef pair<ll, ll > pi; typedef pair<pair<ll, ll >, ll > pii; vector<ll > vec; vector<vector<ll > > vec2; ll MOD = 1000000007; ll INF = 1145141919454519; int main(){ ll N, d, K; cin >> N >> d >> K; //Nと段数 vector<vector<ll > > dp(319, vector<ll >(191919, 0)); dp[0][0] = 1; ll s = 0; ll e = 1; for(ll i = 0; i < N; i++){ //5 //cout << i << endl; ll t_s, t_e; for(ll j = s; j < e; j++){ for(ll h = 1; h <= d; h++){ //cout << "yes" << endl; if(j + h + (N-i-1) * d < K) continue; else{ dp[i+1][j+h] += dp[i][j]; if(j == s) t_s = j + h; break; } } if(j+1+d > K) continue; dp[i+1][j+1+d] += -dp[i][j]; t_e = j + 1 + d; //cout << t_e << " "; } //cout << endl; //累積和 // for(ll i = 0; i <= N; i++){ // for(ll j = 0; j <= K; j++){ // cout << dp[i][j] << " "; // } // cout << endl; // } // cout << endl; s = t_s; e = t_e; //cout << s << " " << e << endl; for(ll j = s; j <= e; j++){ dp[i+1][j] += dp[i+1][j-1]; dp[i+1][j] %= MOD; } //cout << endl; } // for(ll i = 0; i <= N; i++){ // for(ll j = 0; j <= K; j++){ // cout << dp[i][j] << " "; // } // cout << endl; // } if(dp[N][K] < 0){ dp[N][K] += MOD; } cout << dp[N][K] << endl; }