Submission #1338001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338001		AhmadAlhussain	Linear Garden (IOI08_linear_garden)	C++20	85 / 100	113 ms	131072 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,m;
int dp[N][3][3];
bool vis[N][3][3];
int cnt=1;
string s;
int rec(int st,int x,int y) {
    if(vis[st][-x][y]) {
        vis[st][-x][y]=true;
        return dp[st][-x][y];
    }
    if(st==n) {
        return dp[st][-x][y]=1;
    }
    vis[st][-x][y]=true;
    if(x>-2) {
        dp[st][-x][y]+=rec(st+1,x-1,max(y-1,0ll));
    }
    if(y<2) {
        dp[st][-x][y]+=rec(st+1,min(x+1,0ll),y+1);
    }
    return dp[st][-x][y]%=m;
}
void rec1(int st,int x,int y) {
    if(st==n)return;
    if(s[st]=='P') {
        cnt+=dp[st+1][-(x-1)][max(y-1,0ll)];
        cnt%=m;
        rec1(st+1,min(x+1,0ll),y+1);
    }
    else {
        rec1(st+1,x-1,max(y-1,0ll));
    }
}
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n>>m>>s;
    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