Submission #219710

#	Time	Username	Problem	Language	Result	Execution time	Memory
219710		mohamedsobhi777	Linear Garden (IOI08_linear_garden)	C++14	55 / 100	50 ms	65540 KiB

linear_garden

#include <bits/stdc++.h> 

using namespace std ; 
const int N = 2e5 + 7 ; 
long long n , mod , ans ; 
string s ; 

int mv2[2] = {0 , 1} , mv1[2] = {1 , 0} ; 

long long add (long long a , long long b){
    return (a%mod + b%mod + mod) %mod ; 
}

int dp[N][3][3][3][3];

void normalize(int &a , int &b , int &A , int &B){
    int mn = min(a , b) ; 
    a-=mn ; 
    b-=mn; 
    A = max( A , a - b ); 
    B = max(B , b - a); 
}

int solve(int i , short a , short b , short A , short B){
    if(dp[i][a][b][A][B]!=-1)
        return dp[i][a][b][A][B] ; 
    if( a + B > 2 || b + A > 2 ) return 0 ; 
    if(i==n){
        return 1 ; 
    }
    long long ret = 0 ; 
    for(int j = 0 ; j< 2 ;j++){
        int na = a + mv1[j] ; 
        int nb = b + mv2[j] ; 
        int tmpA = A; 
        int tmpB = B; 
        normalize(na , nb , tmpA , tmpB) ; 
        ret= add(ret , solve(i+1 , na , nb , tmpA , tmpB)) ; 
    }
    return dp[i][a][b][A][B] = ret ; 
}

int main(){
    memset(dp , -1 , sizeof dp) ; 
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ; 
    cin>>n>>mod ; 
    cin>> s ; 

    int a = 0, b =0; 
    int A = 0, B = 0; 
    for(int i = 0 ;i < n;i++){
        if(s[i] == 'L'){
            b++ ; 
            normalize(a , b , A , B) ; 
        }else{  
            int tmpa = a ; 
            int tmpb = b ; 
            int tmpA = A ; 
            int tmpB = B ; 
            tmpb++ ; 
            normalize(tmpa , tmpb , tmpA , tmpB) ;
            ans+=solve(i+1 , tmpa , tmpb , tmpA , tmpB) ; 
            a++; 
            normalize(a , b , A , B) ;             
        }
    }
    cout<<add(ans , 1); 
    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: 0 / 5
• Subtask 16: 0 / 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