Submission #423518

#	Time	Username	Problem	Language	Result	Execution time	Memory
423518		Bill_00	Linear Garden (IOI08_linear_garden)	C++14	2 / 100	55 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;
long long u[1000005][5][5];
char s[2000000];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
  	cout.tie(0);
	long long n,m;
	cin >> n >> m;
	for(int i=0;i<n;i++) cin >> s[i];
	u[2][2][2]=1;
	for(int i=1;i<=n;i++){
		int o=0;
		u[i][4][2]=(u[i-1][3][2]+u[i-1][3][1])%m;
		u[i][4][1]=u[i-1][3][0];
		u[i][3][2]=(u[i-1][2][2]+u[i-1][2][1])%m;
		u[i][3][1]=(u[i-1][4][2]+u[i-1][2][0])%m;
		u[i][3][0]=u[i-1][4][1];
		u[i][2][1]=(u[i-1][2][2]+u[i-1][3][2])%m;
		u[i][2][0]=(u[i-1][2][1]+u[i-1][3][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+2][k+2])%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:20:7: warning: unused variable 'o' [-Wunused-variable]
   20 |   int o=0;
      |       ^

• Subtask 1: 2 / 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