結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2018-06-11 03:22:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 5,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 943 ms |
コンパイル使用メモリ | 97,908 KB |
実行使用メモリ | 34,436 KB |
最終ジャッジ日時 | 2024-06-30 13:27:53 |
合計ジャッジ時間 | 1,991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <cmath>#include <iostream>#include <vector>#include <queue>#include <map>#include <set>#include <algorithm>#include <utility>#include <iomanip>#define int long long int#define rep(i, n) for(int i = 0; i < (n); ++i)using namespace std;typedef pair<int, int> P;const int INF = 1e15;const int MOD = 1e9+7;signed main(){int n;cin >> n;vector<vector<int>> dp(3, vector<int>(n+3));dp[0][1] = 1;dp[1][2] = 1;dp[2][3] = 1;for(int i = 2; i <= n; i++){dp[0][i] = (dp[1][i-1] + dp[2][i-1]) % MOD;if(i >= 3){dp[1][i] = (dp[0][i-2] + dp[2][i-2]) % MOD;}if(i >= 4){dp[2][i] = (dp[0][i-3] + dp[1][i-3]) % MOD;}}int ans = ((dp[0][n] + dp[1][n]) % MOD + dp[2][n]) % MOD;cout << ans << endl;return 0;}