Submission #99530

#	Time	Username	Problem	Language	Result	Execution time	Memory
99530		figter001	Linear Garden (IOI08_linear_garden)	C++17	90 / 100	142 ms	66560 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e6+50;

int n,mod;
string s;
int dp[nax][3][3];

int calc(int idx,int a,int b){
	if(a < 0)a = 0;
	if(b < 0)b = 0;
	if(a == 3)return 0;
	if(b == 3)return 0;
	if(idx == n)
		return 1;
	int &ret = dp[idx][a][b];
	if(ret != -1)
		return ret;
	ret = 0;
	ret = (calc(idx+1,a+1,b-1) + calc(idx+1,a-1,b+1)) % mod;
	return ret;
}

int ans;

void solve(int idx,int a,int b){
	if(a < 0)a = 0;
	if(b < 0)b = 0;
	if(a == 3)return;
	if(b == 3)return;
	if(idx == n)
		return;
	if(s[idx] == 'P'){
		ans = (ans + calc(idx+1,a+1,b-1)) % mod;
		solve(idx+1,a-1,b+1);
	}else{
		solve(idx+1,a+1,b-1);
	}
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>mod>>s;
	calc(0,0,0);
	solve(0,0,0);
	cout << (ans + 1)%mod << endl;
}

• 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: 0 / 5
• Subtask 23: 0 / 5