제출 #525835

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525835		Deepesson	Linear Garden (IOI08_linear_garden)	C++17	65 / 100	68 ms	65540 KiB

linear_garden

#include <bits/stdc++.h>

int N,M;
#define MAX 1100000
bool existe[MAX][33][5][2];
int tab[MAX][33][5][2];
int base=2;
std::string s;
int dp(int pos,int pente,int soma,bool desceu){

    int atual = soma;

    for(int i=0;i!=5;++i){

        if(pente&(1<<i)){

            int k = i-2;

            int x = atual-k;

            if(x<-2||x>2){return 0;}

        }

    }

    if(pos==N){

        return 1;

    }

    if(existe[pos][pente][soma+2][desceu])return tab[pos][pente][soma+2][desceu];

    existe[pos][pente][soma+2][desceu]=true;

    if(desceu){

        int alpha=0,beta=0;

        if(atual<2){
            alpha=dp(pos+1,pente|(1<<(soma+3)),soma+1,1);
        }

        if(atual>-2){
            beta=dp(pos+1,pente|(1<<(soma+1)),soma-1,1);
        }

        return tab[pos][pente][soma+2][desceu] = ( alpha + beta ) % M;

    }else {

        if(s[pos]=='L'){

            if(atual>-2){///Aperta L
                return tab[pos][pente][soma+2][desceu] = dp(pos+1,pente|(1<<(soma+1)),soma-1,0);
            }

            else return 0;

        }else {

            int alpha=0,beta=0;

            if(atual<2){///Aperta P
                assert(atual+3<5);
                alpha=dp(pos+1,pente|(1<<(soma+3)),soma+1,0);
            }

            if(atual>-2){///Aperta L
                beta=dp(pos+1,pente|(1<<(soma+1)),soma-1,1);
            }

            return tab[pos][pente][soma+2][desceu] = ( alpha + beta ) % M;

        }
    }
}
int main()
{
    std::cin>>N>>M>>s;
    std::cout<<dp(0,(1<<2),0,0)<<"\n";
}

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