| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 168560 | DavidDamian | Linear Garden (IOI08_linear_garden) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include<stack>
using namespace std;
///Dynamic Programming
///Determine the position of a given string
int memo[2][5][5][5];
int n,m;
int A[1000005];
//The string cannot exceed 2 between L and P, so we keep variables Max and Min
struct node
{
int i,Min,Max,act;
};
stack<node> S; //Stack to keep track of the next node we have to add to the answer
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++){
char plant;
cin>>plant;
if(plant=='L') A[i]=1;
else A[i]=2;
}
int Min=2,Max=2,act=2;
for(int i=0;i<n;i++){
if(A[i]==2){ //If we choose letter P, then we add all the subtree rooted next L to the answer
node x={i+1,min(Min,act+1),max(Max,act+1),act+1};
S.push(x); //So we add that node to the stack
Max=max(Max,act-1);
Min=min(Min,act-1);
act=act-1;
}
else{
Max=max(Max,act+1);
Min=min(Min,act+1);
act=act+1;
}
}
for(int Min=0;Min<3;Min++){ //We compute the base cases
for(int Max=2;Max<5;Max++){
for(int act=0;act<5;act++){
if(act>Max || act<Min) continue;
if(Max-Min>2) memo[(n)%2][Min][Max][act]=0;
else memo[(n)%2][Min][Max][act]=1;
}
}
}
int position=0;
if(S.size() && S.top().i==n){ //If one base case is required, we add it
node x=S.top();S.pop();
position+=memo[(x.i)%2][x.Min][x.Max][x.act];
position%=m;
}
for(int i=n-1;i>=0;i--){ //Computes all non base cases
for(int Min=0;Min<3;Min++){
for(int Max=2;Max<5;Max++){
for(int act=0;act<5;act++){
if(act>Max || act<Min) continue;
int a=0,b=0;
node L={(i+1)%2,min(Min,act+1),max(Max,act+1),act+1};
if(L.Max-L.Min<=2 && L.Min>=0 && L.Max<=4 && L.act<=4); //Ckecks if it can sum the left node
a=memo[L.i][L.Min][L.Max][L.act];
node R={(i+1)%2,min(Min,act-1),max(Max,act-1),act-1};
if(R.Max-R.Min<=2 && R.Min>=0 && R.Max<=4 && R.act<=4); /Checks if it can sum the right node
b=memo[R.i][R.Min][R.Max][R.act];
memo[i%2][Min][Max][act]=(a+b)%m;
}
}
}
if(S.size() && S.top().i==i){ //If it requires the i-th level, then we add it to the sum
node x=S.top();S.pop();
position+=memo[(x.i)%2][x.Min][x.Max][x.act];
position%=m;
}
}
position=position+1; //We add one (The given string)
position%=m;
cout<<position<<'\n';
return 0;
}