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 |
|
|
|
|
|
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 |