Submission #423508

#	Time	Username	Problem	Language	Result	Execution time	Memory
423508		Bill_00	Linear Garden (IOI08_linear_garden)	C++14	70 / 100	175 ms	65540 KiB

linear_garden

#include <bits/stdc++.h>
#define pb push_back
#define pp push
#define ff first
#define ss second
#define ll long long
#define mp make_pair
using namespace std;
unordered_map<long long,unordered_map<long long,unordered_map<long long,long long> > >u;
string s;
int main(){
	long long n,m;
	cin >> n >> m;
	cin >> s;
	u[0][0][0]=1;
	for(int i=1;i<=n;i++){
		int o=0;
		u[i][2][0]=(u[i-1][1][0]+u[i-1][1][-1])%m;
		u[i][2][-1]=u[i-1][1][-2];
		u[i][1][0]=(u[i-1][0][0]+u[i-1][0][-1])%m;
		u[i][1][-1]=(u[i-1][2][0]+u[i-1][0][-2])%m;
		u[i][1][-2]=u[i-1][2][-1];
		u[i][0][-1]=(u[i-1][0][0]+u[i-1][1][0])%m;
		u[i][0][-2]=(u[i-1][0][-1]+u[i-1][1][-1])%m;
	}
	int mx=0,mn=0;
	long long ans=0;
	for(int i=0;i<n-1;i++){
		if(s[i]=='L'){
			mx+=1;
			mn=min(mn+1,0);
			continue;
		}
		int mx_=mx+1;
		int mn_=min(mn+1,0);
		for(int j=0;j<=2-mx_;j++){
			for(int k=0;k>=-2-mn_;k--){
				ans=(ans+u[n-i-1][j][k])%m;
				//cout << n-i-1 << ' ' << j << ' ' << k << ' ' << u[n-i-1][j][k] << endl;
			}
		}
		mx=max(0,mx-1);
		mn--;
	}
	if(s[n-1]=='P'){
		if(mx!=2) ans++; 
	}
	ans++;
	cout << ans%m;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:17:7: warning: unused variable 'o' [-Wunused-variable]
   17 |   int o=0;
      |       ^

• 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: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5