oj.uz

답안 #78754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78754 2018-10-08T13:35:47 Z doowey Linear Garden (IOI08_linear_garden) C++14
100 / 100
 502 ms 6884 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin(),(x).end())
#define len(x) ((int)(x).size())

const int N = (int)1e6 + 2;
int dp[2][3][3][5][2];

int mod;

bool ok(int li, int ri, int cur){
	return max(ri, cur) - min(li, cur) <= 2;
}

void add(int &a, int b){
	a += b;
	if(a >= mod)
		a -= mod;
}

int main(){
	fastIO;
	int n;
	cin >> n >> mod; // L < P
	string s;
	cin >> s ;
	int bit = 1;
	dp[0][2][0][2][0] = 1;
	int li, ri;
	int state;
	for(int i = 0; i < n;i ++ ){
		for(int a = -2; a <= 0; a ++ ){
			for(int b = 0; b <= 2; b ++ ){
				for(int cur = -2; cur <= 2; cur ++ ){
					for(int z = 0; z < 2; z ++ ){
						li = min(a, cur);
						ri = max(b, cur);
						if(ri - li > 2)
							continue;
						state = z;
						if(ok(a, b, cur - 1)){
							add(dp[bit][min(a, cur - 1) + 2][b][cur - 1 + 2][(state || s[i] == 'P')], dp[!bit][a + 2][b][cur + 2][state]);
						}
						if(ok(a, b, cur + 1) and (s[i] != 'L' or state == 1)){
							add(dp[bit][a + 2][max(b, cur + 1)][cur + 3][state], dp[!bit][a + 2][b][cur + 2][state]);
						}
					}
				}
			}
		}
		
		bit = !bit;
		
		for(int a = 0; a <= 2; a ++ ){
			for(int b = 0; b <= 2 ; b ++ ){
				for(int cur = 0; cur < 5; cur ++ ){
					for(int z = 0; z < 2; z ++ ){
						dp[bit][a][b][cur][z] = 0;
					}
				}
			}
		}
	
	}
	int ans = 0;
	for(int a = 0; a < 3; a ++ ){
		for(int b = 0; b < 3; b ++ ){
			for(int cur = 0; cur < 5; cur ++ ){
				for(int z = 0; z < 2; z ++ ){
					add(ans, dp[!bit][a][b][cur][z]);
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 728 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 3 ms 764 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 776 KB Output is correct
2 Correct 3 ms 776 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 776 KB Output is correct
2 Correct 4 ms 780 KB Output is correct
3 Correct 4 ms 788 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 796 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 828 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1052 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1188 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 1928 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 2376 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 2780 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 3944 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 456 ms 4924 KB Output is correct
2 Correct 488 ms 5904 KB Output is correct
3 Correct 502 ms 6884 KB Output is correct