Submission #1477603


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 (!(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 0
Code Size 1632 Byte
Status WA
Exec Time 4 ms
Memory 8576 KB

Judge Result

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