oj.uz

Submission #168561

# Submission time Handle Problem Language Result Execution time Memory
168561 2019-12-13T18:06:07 Z DavidDamian Linear Garden (IOI08_linear_garden) C++11
100 / 100
 287 ms 13448 KB 
#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;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:62:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                     if(L.Max-L.Min<=2 && L.Min>=0 && L.Max<=4 && L.act<=4); //Ckecks if it can sum the left node
                     ^~
linear_garden.cpp:63:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                         a=memo[L.i][L.Min][L.Max][L.act];
                         ^
linear_garden.cpp:65:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                     if(R.Max-R.Min<=2 && R.Min>=0 && R.Max<=4 && R.act<=4); //Checks if it can sum the right node
                     ^~
linear_garden.cpp:66:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                         b=memo[R.i][R.Min][R.Max][R.act];
                         ^

Subtask #1
2.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 13372 KB Output is correct
2 Correct 284 ms 13448 KB Output is correct
3 Correct 279 ms 13448 KB Output is correct