Submission #741773

#	Time	Username	Problem	Language	Result	Execution time	Memory
741773		MODDI	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	95 ms	3324 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, mod;
string str;
// 'L' < 'P'
int dp[2][3][3][2];
void add(int &x, int val){
	x += val;
	if(x >= mod)
		x-= mod;
}
int 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(0, mi- 1)][ma + 1][1], dp[i%2][mi][ma][1]);
                        add(dp[(i+1)%2][max(0, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                    } else {
                        add(dp[(i+1)%2][max(0, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                        add(dp[(i+1)%2][max(0, 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(0, ma - 1)][1], dp[i%2][mi][ma][1]);
                        add(dp[(i+1)%2][mi + 1][max(0, ma - 1)][0], dp[i%2][mi][ma][0]);
                    } else {
                        add(dp[(i+1)%2][mi + 1][max(0, 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<<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: 5 / 5
• Subtask 23: 5 / 5