結果
問題 |
No.533 Mysterious Stairs
|
ユーザー |
![]() |
提出日時 | 2017-06-23 23:00:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 702 ms |
コンパイル使用メモリ | 89,344 KB |
実行使用メモリ | 34,380 KB |
最終ジャッジ日時 | 2024-10-04 07:48:32 |
合計ジャッジ時間 | 1,779 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<iostream> #include<iomanip> #include<math.h> #include<algorithm> #include<string> #include<vector> #include<queue> #include<set> #include<map> #include<tuple> #include<complex> #define REP(i, N) for(ll i = 0; i < N; ++i) #define FOR(i, a, b) for(ll i = a; i < b; ++i) #define ALL(a) (a).begin(),(a).end() #define pb push_back #define INF (long long)1000000000 #define MOD 1000000007 #define EPS (long double) 1e-8 using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll, ll> P; int dh[4] = {1, 0, -1, 0}; int dw[4] = {0, 1, 0, -1}; using namespace std; int main() { int n; cin>>n; vector<vector<ll> > dp(3, vector<ll>(n + 1, 0)); dp[0][0] = 1; dp[1][0] = 1; dp[2][0] = 1; FOR(i, 1, n + 1) { if(i == 1) dp[0][i] = 1; else dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % MOD;; if(i > 1) { if(i == 2) dp[1][i] = 1; else dp[1][i] = (dp[0][i - 2] + dp[2][i - 2]) % MOD; } if(i > 2) { if(i == 3) dp[2][i] = 1; else dp[2][i] = (dp[0][i - 3] + dp[1][i - 3]) % MOD; } } ll res = dp[0][n] + dp[1][n] + dp[2][n]; res = res % MOD; cout<<res<<endl; }