第11回日本情報オリンピック 予選(オンライン)

Submission #1477666

Source codeソースコード

#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

Task問題 D - パスタ (Pasta)
User nameユーザ名 Nafmo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1709 Byte
File nameファイル名
Exec time実行時間 4 ms
Memory usageメモリ使用量 8576 KB

Test case

Set

Set name Score得点 / Max score Cases
set01 20 / 20 data1
set02 20 / 20 data2
set03 20 / 20 data3
set04 20 / 20 data4
set05 20 / 20 data5

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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