oj.uz

Submission #410400

# Submission time Handle Problem Language Result Execution time Memory
410400 2021-05-22T16:03:44 Z Jasiekstrz Linear Garden (IOI08_linear_garden) C++17
100 / 100
 77 ms 37596 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e6;
int mod;
int dp[N+10][3][3];
int ask(int n,int l,int r)
{
	if(r+l>2)
		return 0;
	if(r+l==2)
		return dp[n][l][r];
	// l=0, r=1
	return (dp[n][0][2]+dp[n][1][1]-dp[n][0][1])%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n>>mod;
	for(int j=0;j<=2;j++)
	{
		for(int k=0;k<=2;k++)
			dp[0][j][k]=1;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=2;j++)
		{
			for(int k=0;k<=2;k++)
			{
				if(j-1>=0 && k+1<=2)
				{
					dp[i+1][j-1][k+1]+=dp[i][j][k];
					dp[i+1][j-1][k+1]%=mod;
				}
				if(k-1>=0 && j+1<=2)
				{
					dp[i+1][j+1][k-1]+=dp[i][j][k];
					dp[i+1][j+1][k-1]%=mod;
				}
			}
		}
	}
	string s;
	cin>>s;
	int ans=1;
	int sum=0;
	int l=0,r=0;
	for(int i=1;i<=n;i++)
	{
		int x=(s[i-1]=='L' ? -1:1);
		if(x==1)
		{
			int tmps=sum-1,tmpl=max(l,-tmps),tmpr=max(r,tmps);
			ans+=ask(n-i,tmpl+tmps,tmpr-tmps);
			ans%=mod;
		}		
		sum+=x;
		l=max(l,-sum);
		r=max(r,sum);
	}
	cout<<(ans%mod+mod)%mod<<"\n";
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 252 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 324 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2508 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3104 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 11864 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15064 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 19040 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23412 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 36644 KB Output is correct
2 Correct 77 ms 37596 KB Output is correct
3 Correct 71 ms 37596 KB Output is correct