Submission #777873

#	Time	Username	Problem	Language	Result	Execution time	Memory
777873		raysh07	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	70 ms	3312 KiB

linear_garden

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

int n, mod;
string str;

int dp[2][3][3][2];
void add(int &x, int val){
	x += val;
	if(x >= mod)
		x-= mod;
}

int32_t main(){
	cin >> n >> mod >> str;

	dp[0][0][0][1] = 1;
	for(int i = 0; i < n; i++){
		char c = str[i];
		for(int mi = 0; mi <= 2; mi++){
			for(int ma = 0; ma <= 2; ma++){
			 if(ma != 2) {
                if(c == 'L') {
                    add(dp[(i+1)%2][max(0LL, mi- 1)][ma + 1][1], dp[i%2][mi][ma][1]);
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                } else {
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][1]);
                }
            }
            if(mi != 2) {
                if(c == 'P') {
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][1], dp[i%2][mi][ma][1]);
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][0], dp[i%2][mi][ma][0]);
                } else {
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][0], dp[i%2][mi][ma][0]);
                }
            }
            dp[i%2][mi][ma][0] = dp[i%2][mi][ma][1] = 0;
			}
		}
	}

	int sum = 0;
	for(int mi = 0; mi <= 2; mi++){
		for(int ma = 0; ma <= 2; ma++){
			add(sum, dp[n%2][mi][ma][0]);
			add(sum, dp[n%2][mi][ma][1]);
		}
	}

	cout << sum << "\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