Submission #237277

#	Time	Username	Problem	Language	Result	Execution time	Memory
237277		nikatamliani	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	68 ms	3736 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, ZERO = 2;
int n, MOD, dp[N][15], ans, something;
int code[10][10][10], codes;
string s;
int leftMIN, leftMAX, leftDiff;
int &safeDP(int index, int MIN, int MAX, int diff){
	int c = code[MIN][MAX][diff];
	return (~c) ? dp[index][c] : something;
}
int main(){
	cin >> n >> MOD >> s;
	s = "@" + s;
	memset(code, -1, sizeof code);
	for(int MIN = -2; MIN <= 0; ++MIN){
		for(int MAX = 0; MAX <= 2; ++MAX){
			for(int diff = -2; diff <= 2; ++diff){
				if(!(MAX - MIN > 2 || diff > MAX || diff < MIN)){
					code[MIN][MAX][diff] = codes++;
				}
			}
		}
	}
	safeDP(n + 1, 0, 0, 0) = 1;
	for(int i = n + 1; i >= 1; --i){
		for(int MIN = -2; MIN <= 0; ++MIN){
			for(int MAX = 0; MAX <= 2; ++MAX){
				if(MAX - MIN > 2)break;
				for(int diff = MIN; diff <= MAX; ++diff){
					int cur = safeDP(i, MIN, MAX, diff);
					int newMIN = min(MIN, diff - 1), newMAX = max(MAX, diff + 1);
					int &dp1 = safeDP(i - 1, newMIN, MAX, diff - 1);
					int &dp2 = safeDP(i - 1, MIN, newMAX, diff + 1);
					if(MAX - newMIN <= 2) dp1 += cur;
					if(newMAX - MIN <= 2) dp2 += cur;
					if(dp1 >= MOD)dp1 -= MOD;
					if(dp2 >= MOD)dp2 -= MOD;  
				}
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		if(s[i] == 'P'){
			int fakeDiff = leftDiff, fakeMAX = leftMAX, fakeMIN = leftMIN;
			fakeDiff--;
			fakeMAX = max(fakeMAX, fakeDiff);
			fakeMIN = min(fakeMIN, fakeDiff);
			for(int rightMIN = -2; rightMIN <= 0; ++rightMIN){
				for(int rightMAX = 0; rightMAX <= 2; ++rightMAX){
					if(rightMAX - rightMIN > 2)break;
					for(int rightDiff = rightMIN; rightDiff <= rightMAX; rightDiff++){
						int allDiff = rightDiff + fakeDiff;
						int allMIN = min(fakeMIN, rightMIN + fakeDiff);
						int allMAX = max(fakeMAX, rightMAX + fakeDiff);
						if(allMAX - allMIN > 2 || allMIN > allDiff || allMAX < allDiff)continue;
						int &cur = safeDP(i + 1, rightMIN, rightMAX, rightDiff);
						ans += cur;
						if(ans >= MOD)ans -= MOD;
					}
				}
			}
		}
		if(s[i] == 'P')leftDiff++;
		if(s[i] == 'L')leftDiff--;
		leftMIN = min(leftMIN, leftDiff);
		leftMAX = max(leftMAX, leftDiff);
	}
	ans = (ans + 1) % MOD;
	cout << ans << '\n';
} 

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5