Submission #249227

#	Time	Username	Problem	Language	Result	Execution time	Memory
249227		eohomegrownapps	Linear Garden (IOI08_linear_garden)	C++14	40 / 100	1597 ms	62976 KiB

linear_garden

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

ll m;

ll 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 (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 {
        return ((cur-1<s?0:dp(len-1,s,e,cur-1))+(cur+1>e?0:dp(len-1,s,e,cur+1)))%m;
    }
}


int main(){
    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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 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