제출 #1338014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338014		AhmadAlhussain	Linear Garden (IOI08_linear_garden)	C++20	90 / 100	158 ms	118792 KiB

linear_garden

#include<iostream>
using namespace std;
const int N = 1000005;
int n,m;
int dp[N][6];
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]=1,c[1][0]=2,c[1][1]=3,c[2][0]=4,c[0][2]=5;
    rec(0,0,0);
    rec1(0,0,0);
    cout<<cnt<<'\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: 0 / 5
• Subtask 23: 0 / 5