Submission #249233

#	Time	Username	Problem	Language	Result	Execution time	Memory
249233		eohomegrownapps	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	146 ms	54136 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int m;

int dpv[1000000][3];

int dp(int len, int s, int e, int cur){
	//can we go up?
    //cout<<len<<" "<<s<<" "<<e<<" "<<cur<<'\n';
    if (!(s<=cur&&cur<=e)||(e-s>2)){
        return 0;
    }
    if (e-s==2&&len%2==0&&dpv[len/2][cur-s]!=-1){
        return dpv[len/2][cur-s];
    }
    if (len==0){
        return 1;
    }
    if (e-s<2){
        return (dp(len-1,min(s,cur-1),e,cur-1)+dp(len-1,s,max(e,cur+1),cur+1))%m;
    } else {
        if (len%2==0){
            return dpv[len/2][cur-s]=((cur-1<s?0:dp(len-1,s,e,cur-1))+(cur+1>e?0:dp(len-1,s,e,cur+1)))%m;
        } else {
            return ((cur-1<s?0:dp(len-1,s,e,cur-1))+(cur+1>e?0:dp(len-1,s,e,cur+1)))%m;
        }
        
    }
}

void initdp(){
    for (int i = 0; i<500000; i++){
        //for (int j = 0; j<3; j++){
            for (int k = 0; k<3; k++){
                dpv[i][k]=-1;
            }
        //}
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    initdp();
    int n;
    cin>>n;
    cin>>m;
    int curmin = 0;
    int curmax = 0;
    int curval = 0;
    ll ind = 1;
    for (int i = 0; i<n; i++){
        char c;
        cin>>c;
        bool val = (c=='P');
        if (val){
            ind+=dp(n-i-1,min(curmin,curval-1),max(curmax,curval-1),curval-1);
            ind%=m;
            curval++;
        } else {
            curval--;
        }
        curmin=min(curmin,curval);
        curmax=max(curmax,curval);
    }
    cout<<ind<<'\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: 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