Submission #168552

#	Time	Username	Problem	Language	Result	Execution time	Memory
168552		DavidDamian	Linear Garden (IOI08_linear_garden)	C++11	75 / 100	80 ms	40952 KiB

linear_garden

#include <iostream>
using namespace std;
///Dynamic Programming
///Determine the position of a given string
int memo[100005][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
int garden(int i,int Max,int Min,int act) ///Return the number of strings in the subtree rooted i,Max,Min,act
{
    if(Min<0 || Max>4 || (Max-Min)>2) //Not valid choose
        return 0;
    if(i==n) //Valid choose
        return memo[i][Max][Min][act]=1;
    if(memo[i][Max][Min][act]==0){
        memo[i][Max][Min][act]=garden(i+1,max(Max,act+1),min(Min,act+1),act+1)+
                                garden(i+1,max(Max,act-1),min(Min,act-1),act-1);
        memo[i][Max][Min][act]%=m;
    }
    return memo[i][Max][Min][act];
}
int main()
{
    cin>>n>>m;
    if(n>100000){
        cout<<0<<'\n';
        return 0;
    }
    for(int i=0;i<n;i++){
        char plant;
        cin>>plant;
        if(plant=='L') A[i]=1;
        else A[i]=2;
    }
    int position=0;
    int Min=2,Max=2,act=2;
    garden(0,2,2,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
            position+=memo[i+1][max(Max,act+1)][min(Min,act+1)][act+1];
            position%=m;
            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;
        }
    }
    position=position+1; //We add one (The given string)
    position%=m;
    cout<<position<<'\n';
    return 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: 5 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5