結果
問題 | 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-8using 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;}