結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2017-08-22 20:05:58 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 1,738 bytes |
コンパイル時間 | 655 ms |
コンパイル使用メモリ | 66,996 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-15 04:26:10 |
合計ジャッジ時間 | 1,559 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <iostream>#include <queue>using namespace std;const int mod = 1e9+7;int main(void){int n;long long dp[100000][4];queue<long long> memo[4];cin >> n;if(n==1){cout << "1" << endl;return 0;}if(n == 2){cout << "1" << endl;return 0;}memo[1].push(1);memo[2].push(0);memo[3].push(0);memo[1].push(0);memo[2].push(1);memo[3].push(0);memo[1].push(1);memo[2].push(1);memo[3].push(1);long long m[5][4];for(int i=4; i<=n; i++){m[1][1] = memo[1].front();m[1][2] = memo[2].front();m[1][3] = memo[3].front();memo[1].pop();memo[2].pop();memo[3].pop();m[2][1] = memo[1].front();m[2][2] = memo[2].front();m[2][3] = memo[3].front();memo[1].pop();memo[2].pop();memo[3].pop();m[3][1] = memo[1].front();m[3][2] = memo[2].front();m[3][3] = memo[3].front();memo[1].pop();memo[2].pop();memo[3].pop();m[4][3] = (m[1][2] + m[1][1])%mod;m[4][2] = (m[2][1] + m[2][3])%mod;m[4][1] = (m[3][2] + m[3][3])%mod;memo[1].push(m[2][1]);memo[2].push(m[2][2]);memo[3].push(m[2][3]);memo[1].push(m[3][1]);memo[2].push(m[3][2]);memo[3].push(m[3][3]);memo[1].push(m[4][1]);memo[2].push(m[4][2]);memo[3].push(m[4][3]);}memo[1].pop();memo[2].pop();memo[3].pop();memo[1].pop();memo[2].pop();memo[3].pop();cout << (memo[1].front()+memo[2].front()+memo[3].front())%mod << endl;return 0;}