Submission #799667

#	Time	Username	Problem	Language	Result	Execution time	Memory
799667		mosiashvililuka	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	95 ms	65008 KiB

linear_garden

#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 / 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: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5