Submission #249222

#	Time	Username	Problem	Language	Result	Execution time	Memory
249222		eohomegrownapps	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	41 ms	65540 KiB

linear_garden

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

ll m;

ll dpv[1000000][3][3];

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 (dpv[len][e-s][cur-s]!=-1){
        return dpv[len][e-s][cur-s];
    }
    if (len==0){
        return dpv[len][e-s][cur-s]=1;
    }
    if (e-s<2){
        return dpv[len][e-s][cur-s]=(dp(len-1,min(s,cur-1),e,cur-1)+dp(len-1,s,max(e,cur+1),cur+1))%m;
    } else {
        return dpv[len][e-s][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;
    }
}

void initdp(){
    for (int i = 0; i<1000000; i++){
        for (int j = 0; j<3; j++){
            for (int k = 0; k<3; k++){
                dpv[i][j][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: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 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