Submission #3537267


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
	int H, W, K; 
	cin >> H >> W >> K; 
	long long int dp[100][10] = {}; 
	long long int P = 1e9 + 7; 
	int Fib[8] = {1, 1, 2, 3, 5, 8, 13, 21}; 
	if(W == 1){cout << 1 << endl; }
	else{
	dp[0][1] = 1; 
	for(int i = 1; i < 105; i++){
		dp[i][1] = ((dp[i-1][1] * Fib[W-1]) % P + (dp[i-1][2] * Fib[W-2]) % P) % P; 
		dp[i][W] = ((dp[i-1][W] * Fib[W-1]) % P + (dp[i-1][W-1] * Fib[W-2]) % P) % P; 
		for(int j = 2; j < W; j++){
			dp[i][j] = ((dp[i-1][j-1] * Fib[j-2] * Fib[W-j]) % P + (dp[i-1][j] * Fib[j-1] * Fib[W-j]) % P + (dp[i-1][j+1] * Fib[j-1] * Fib[W-j-1]) % P ) % P; 
	}
        }
	cout << dp[H][K] << endl; 
	}
}

Submission Info

Submission Time
Task D - Number of Amidakuji
User zundamochi_1117
Language C++14 (GCC 5.4.1)
Score 0
Code Size 734 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:25: warning: iteration 100u invokes undefined behavior [-Waggressive-loop-optimizations]
   dp[i][1] = ((dp[i-1][1] * Fib[W-1]) % P + (dp[i-1][2] * Fib[W-2]) % P) % P; 
                         ^
./Main.cpp:14:19: note: containing loop
  for(int i = 1; i < 105; i++){
                   ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt
All 0 / 400 in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_06.txt
Case Name Status Exec Time Memory
in01.txt
in02.txt
in03.txt
in04.txt
in05.txt
in06.txt 1 ms 256 KB
in07.txt 1 ms 256 KB
in08.txt
in09.txt 1 ms 256 KB
in10.txt
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
sample_05.txt 1 ms 256 KB
sample_06.txt