Submission #1338013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338013		AhmadAlhussain	Linear Garden (IOI08_linear_garden)	C++20	6 / 100	155 ms	114880 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n,m;
int dp[N][5];
int cnt=1;
char s[N];
char c[3][3];
int rec(int st,char x,char y) {
    if(dp[st][c[-x][y]]!=0) {
        return dp[st][c[-x][y]];
    }
    if(st==n) {
        return dp[st][c[-x][y]]=1;
    }
    if(x>-2) {
        dp[st][c[-x][y]]+=rec(st+1,x-1,max(y-1,0));
    }
    if(y<2) {
        dp[st][c[-x][y]]+=rec(st+1,min(x+1,0),y+1);
    }
    return dp[st][c[-x][y]]%=m;
}
void rec1(int st,char x,char y) {
    if(st==n)return;
    if(s[st]=='P') {
        cnt+=dp[st+1][c[-(x-1)][max(y-1,0)]];
        cnt%=m;
        rec1(st+1,min(x+1,0),y+1);
    }
    else {
        rec1(st+1,x-1,max(y-1,0));
    }
}
signed main() {
    //cin.tie(0)->sync_with_stdio(0);
    cin >> n>>m>>s;
    c[0][1]=0,c[1][0]=1,c[1][1]=2,c[2][0]=3,c[0][2]=4;
    rec(0,0,0);
    rec1(0,0,0);
    cout<<cnt<<'\n';

}

• Subtask 1: 2 / 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: 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