oj.uz

Submission #799667

# Submission time Handle Problem Language Result Execution time Memory
799667 2023-07-31T18:25:26 Z mosiashvililuka Linear Garden (IOI08_linear_garden) C++14
100 / 100
 95 ms 65008 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,mod,dp[1000009][4][4],bo1,bo2,x,xx,BO1,BO2,pas,mn,mx,jm;
string s;
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>mod;
    cin>>s;s="0"+s;
    dp[0][0][0]=1;
    for(i=0; i<a; i++){
        for(bo1=0; bo1<=2; bo1++){
            for(bo2=0; bo2<=2; bo2++){
                if(bo1+bo2>2) continue;
                //-1
                BO1=bo1+1;
                BO2=max(bo2-1,0);
                if(BO1<=2){
                    dp[i+1][BO1][BO2]+=dp[i][bo1][bo2];dp[i+1][BO1][BO2]%=mod;
                }
                //1
                BO2=bo2+1;
                BO1=max(bo1-1,0);
                if(BO2<=2){
                    dp[i+1][BO1][BO2]+=dp[i][bo1][bo2];dp[i+1][BO1][BO2]%=mod;
                }
            }
        }
    }

    mn=mx=0;jm=0;
    for(i=1; i<=a; i++){
        if(s[i]=='L'){
            jm--;
            if(jm<0) mn=max(mn,0-jm);
            if(jm>0) mx=max(mx,jm);
            continue;
        }
        
        int MN=mn,MX=mx;
        jm--;
        if(jm<0) mn=max(mn,0-jm);
        if(jm>0) mx=max(mx,jm);
        //
        for(bo1=0; bo1<=2; bo1++){
            for(bo2=0; bo2<=2; bo2++){
                BO1=max(mn,bo1-jm);
                BO2=max(mx,jm+bo2);
                if(BO1+BO2>2) continue;
                pas+=dp[a-i][bo1][bo2];pas%=mod;
            }
        }
        //
        mn=MN;mx=MX;
        jm+=2;
        if(jm<0) mn=max(mn,0-jm);
        if(jm>0) mx=max(mx,jm);
    }
    pas++;pas%=mod;
    cout<<pas;
    return 0;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
2.0 / 2.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

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

Subtask #10
4.0 / 4.0

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

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 65008 KB Output is correct
2 Correct 95 ms 64912 KB Output is correct
3 Correct 88 ms 64976 KB Output is correct