제출 #1008641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008641		vqpahmad	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	42 ms	65536 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define int long long 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n;
int dp[MAXN][5][5][5]; // len, min ,max, cur
int calc(int len, int mn, int mx, int cur){
	if (mx - mn > 2 || cur < 0 || len < 0 || mn < 0 || mx < 0 || len >= MAXN || mn >= 5 || mx >= 5 || cur >= 5) return 0;
	if (dp[len][mn][mx][cur] != -1) return dp[len][mn][mx][cur];
	if (len == 0) return dp[len][mn][mx][cur] = 1;
	return dp[len][mn][mx][cur] = ((calc(len - 1, min(mn, cur - 1), mx, cur - 1) + calc(len - 1, mn, max(mx, cur + 1), cur + 1)) % mod);
}
int32_t main(){
	//memset(dp, -1, sizeof(dp));
	for (int i = 0; i < MAXN; i++)
		for (int j = 0; j < 5; j++)
			for (int k = 0; k < 5; k++)
				for (int l = 0; l < 5; l++)
					dp[i][j][k][l] = -1;
	cin >> n >> mod;
	string s;
	cin >> s;
	int cur_sum = 2, mn = 2, mx = 2;
	int ans = 1;
	for (int i = 0; i < n; i++){
		if (s[i] == 'L'){
			cur_sum--; 
			ckmin(mn, cur_sum);
			continue;
		}
		// now it is P
		cur_sum--;
		ans += calc(n - i - 1, min(cur_sum, mn), mx, cur_sum);
		ans %= mod;
		cur_sum += 2;
		ckmax(mx, cur_sum);
	}
	cout << ans << endl;
}

• 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