제출 #1338009

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

linear_garden

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n,m;
int dp[N][6];
int cnt=1;
char s[N];
map<pair<char,char>,int>mp;
int rec(int st,short x,short y) {
    if(dp[st][mp[{-x,y}]]!=0) {
        return dp[st][mp[{-x,y}]];
    }
    if(st==n) {
        return dp[st][mp[{-x,y}]]=1;
    }
    if(x>-2) {
        dp[st][mp[{-x,y}]]+=rec(st+1,x-1,max(y-1,0));
    }
    if(y<2) {
        dp[st][mp[{-x,y}]]+=rec(st+1,min(x+1,0),y+1);
    }
    return dp[st][mp[{-x,y}]]%=m;
}
void rec1(int st,short x,short y) {
    if(st==n)return;
    if(s[st]=='P') {
        cnt+=dp[st+1][mp[{-(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;
    mp[{0,0}]=0,mp[{0,1}]=1,mp[{1,0}]=2,mp[{1,1}]=3,mp[{2,0}]=4,mp[{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: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5