Submission #480583

#	Time	Username	Problem	Language	Result	Execution time	Memory
480583		tht2005	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	41 ms	65540 KiB

linear_garden

/**
 *	Magician: tht2005
 *	Spawned: 2021.10.17 14:12:11	
**/

#include <bits/stdc++.h>
using namespace std;

int n, md, memo[1000000][5][5][5][2];
string s;

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

int dp(int i, int low, int high, int cur, int tight)
{
	if(high - low > 2) return 0;
	if(i >= n) return 1;
	int& res = memo[i][low][high][cur][tight];
	if(~res) return res;
	res = 0;
	if(tight) {
		add(res, dp(i + 1, min(low, cur - 1), high, cur - 1, 1));
		add(res, dp(i + 1, low, max(high, cur + 1), cur + 1, 1));
	}
	else {
		if(s[i] == 'L') {
			add(res, dp(i + 1, min(low, cur - 1), high, cur - 1, 0));
		}
		else {
			add(res, dp(i + 1, min(low, cur - 1), high, cur - 1, 1));
			add(res, dp(i + 1, low, max(high, cur + 1), cur + 1, 0));
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> md >> s;
	memset(memo, -1, sizeof(memo));
	cout << dp(0, 2, 2, 2, 0);
	return 0;
}

• 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