Submission #78754

#	Time	Username	Problem	Language	Result	Execution time	Memory
78754		doowey	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	502 ms	6884 KiB

linear_garden

#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 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5