Submission #1477666
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using std::cout;
using std::vector;
using std::endl;
using std::cin;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 10000;
const ll INF = 50000000000000000;
typedef std::pair<int, int> P;
ll N, K, A[102];
ll dp[102][102][102];
ll ans;
//x日目:x日目にyを x-1日目にzを 選んだときの通り数
ll DP(int x, int y, int z) {
if (dp[x][y][z] != -1) { return dp[x][y][z]; }
if (x == 1) {
if (A[x] != 0) {
if (y != A[x])return dp[x][y][z] = 0;
}
return dp[x][y][z] = 1;
}
if (A[x] != 0) {
if (y != A[x])return dp[x][y][z] = 0;
}
{
ll res = 0;
if (x - 1 == 1) {
res = DP(x - 1, z, 1)%MOD;
}
else {
if (!(y == z&&y == 1))res += DP(x - 1, z, 1) % MOD;
if (!(y == z&&y == 2))res += DP(x - 1, z, 2) % MOD;
if (!(y == z&&y == 3))res += DP(x - 1, z, 3) % MOD;
}
return dp[x][y][z] = res%MOD;
}
}
int main() {
cin >> N >> K;
REP(i, 102)REP(j, 102)REP(k, 102)dp[i][j][k] = -1;
REP(i, K) {
int a, b;
cin >> a >> b;
A[a] = b;
}
REP(i, 3)REP(j, 3) {
ans += DP(N, i + 1, j + 1);
}
cout << ans%MOD << endl;
}
Submission Info
Submission Time |
|
Task |
D - パスタ (Pasta) |
User |
Nafmo2 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1709 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
8576 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 |
4 ms |
8576 KB |
data2 |
AC |
4 ms |
8576 KB |
data3 |
AC |
4 ms |
8576 KB |
data4 |
AC |
4 ms |
8576 KB |
data5 |
AC |
4 ms |
8576 KB |