Submission #480586

#	Time	Username	Problem	Language	Result	Execution time	Memory
480586		tht2005	Linear Garden (IOI08_linear_garden)	C++14	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][3][3][2];
string s;

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

int dp(int i, int cl, int cp, int tight)
{
	if(i >= n) return 1;
	int& res = memo[i][cl][cp][tight];
	if(~res) return res;
	res = 0;
	if(cl < 2) add(res, dp(i + 1, cl + 1, max(0, cp - 1), tight || s[i] == 'P'));
	if((tight || s[i] == 'P') && cp < 2) add(res, dp(i + 1, max(0, cl - 1), cp + 1, tight));
	return res;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> md >> s;
	memset(memo, -1, sizeof(memo));
	cout << dp(0, 0, 0, 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