Submission #1266337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266337		PlayVoltz	Linear Garden (IOI08_linear_garden)	C++20	0 / 100	110 ms	131072 KiB

linear_garden

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <fstream>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, dp[1000005][3][3][3];
string s;

int garden(int i, int low, int high, int d){
	while (low<0)++low, ++high, ++d;
	while (high>2)--high, --low, --d;
	if (high-low>2)return 0;
	if (i==n-1)return dp[i][low][high][d]=1;
	if (dp[i][low][high][d]!=-1)return dp[i][low][high][d];
	return dp[i][low][high][d]=(garden(i+1, low, max(high, d+1), d+1)+garden(i+1, min(low, d-1), high, d-1))%m;
}

int32_t main(){
	cin>>n>>m>>s;
	memset(dp, -1, sizeof(dp));
	int ans=(garden(0, 0, 1, 1)+garden(0, 1, 2, 1))%m;
	for (int i=0, low=0, high=0, d=0; i<n; ++i){
		if (s[i]=='L')ans=(ans-garden(i, low, max(high, d+1), d+1)+m)%m, --d, low=min(low, d);
		else ++d, high=max(high, d);
	}
	cout<<ans;
}

• 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