제출 #466839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466839		dutch	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	223 ms	2408 KiB

linear_garden

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

int N, M, dp[2][3][3], result;
string S;

#define s(i) (S[i] == 'P')

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> N >> M >> S;

	dp[0][0][0] = 1;

	for(int i=N; --i>=0; ){
		int prev[2][3][3] = {};
		swap(prev, dp);

		for(bool a : {0, 1}){
			for(int x : {0, 1, 2}){
				for(int y : {0, 1, 2}){
					if(x < 2) (dp[!s(i) && a][x + 1][max(y - 1, 0)] += prev[a][x][y]) %= M;
					if(y < 2) (dp[!s(i) || a][max(x - 1, 0)][y + 1] += prev[a][x][y]) %= M;
				}
			}
		}
	}

	for(int x : {0, 1, 2})
		for(int y : {0, 1, 2})
			(result += dp[0][x][y]) %= M;

	cout << result;
}

• 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