| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1266339 | PlayVoltz | Linear Garden (IOI08_linear_garden) | C++20 | 0 ms | 0 KiB |
#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 aa=1000005, bb=3;
int n, m, dp[aa][bb][bb][bb];
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;
}