Submission #1628159


Source Code Expand

#include<iostream>
#include<algorithm>

int dp[101][4][2];
int N, K;
int ans;
int mod = 10000;
int sp[101];
bool de[101];


int main() {
	std::cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		std::cin >> a >> b;
		de[a] = true;
		sp[a] = b;
	}
	if (de[1]) {
		dp[1][sp[1]][0] = 1;
	}
	else {
		dp[1][1][0] = dp[1][2][0] = dp[1][3][0] = 1;
	}
	for (int i = 1; i <= N; i++) {
		if (de[i]) {
			for (int j = 1; j <= 3; j++) {
				if (sp[i] == j) {
					dp[i][sp[i]][1] += dp[i - 1][j][0];
				}
				else {
					dp[i][sp[i]][0] += dp[i - 1][j][1] + dp[i - 1][j][0];
				}
			}
			dp[i][sp[i]][0] %= mod;
			dp[i][sp[i]][1] %= mod;
		}
		else {
			for (int j = 1; j <= 3; j++) {
				for (int k = 1; k <= 3; k++) {
					if (j == k) {
						dp[i][j][1] += dp[i - 1][k][0];
					}
					else {
						dp[i][j][0] += dp[i - 1][k][0] + dp[i - 1][k][1];
					}
				}
				dp[i][j][0] %= mod;
				dp[i][j][1] %= mod;
			}
		}
	}
	for (int i = 1; i <= 3; i++) {
		ans += dp[N][i][0];
		ans += dp[N][i][1];
		ans %= mod;
	}
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Submission Time
Task D - パスタ (Pasta)
User ikefumy
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1124 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name set01 set02 set03 set04 set05
Score / Max Score 20 / 20 20 / 20 20 / 20 20 / 20 20 / 20
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
set01 data1
set02 data2
set03 data3
set04 data4
set05 data5
Case Name Status Exec Time Memory
data1 AC 1 ms 256 KB
data2 AC 1 ms 256 KB
data3 AC 1 ms 256 KB
data4 AC 1 ms 256 KB
data5 AC 1 ms 256 KB