Submission #1336199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336199		eyadooz	Linear Garden (IOI08_linear_garden)	C++20	95 / 100	98 ms	99196 KiB

linear_garden

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'

int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    string a;
    cin >> a;
    int dp[n+5][5][5];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<3;i++) 
        for(int j=0;j<3;j++) dp[n][j][i]=1;

    for(int i=n-1;i>=1;i--) 
    {
        for(int j=0;j<3;j++) 
        {
            for(int d=0;d<3;d++) 
            {
                for(int k=0;k<2;k++) 
                {
                    int dif=(k==0?-1:1);
                    int cur=j+dif, nd=d;
                    if(cur>d) nd++;
                    else if(cur<0) {cur=0;nd++;}
                    if(nd>2) continue;
                    dp[i][j][d]+=dp[i+1][cur][nd];
                    dp[i][j][d]%=m;
                }
            }
        }
    }

    int pos=1, cur=0, s=0;
    for(int i=1;i<=n;i++) 
    {
        if(a[i-1]=='P') 
        {
            int ncur=cur+1, ns=s;
            if(ncur>ns) ns++;
            else if(ncur<0) ncur=0, ns++;
            pos+=dp[i][ncur][ns];
            pos%=m;
        }
        int dif=(a[i-1]=='L'?1:-1);
        cur+=dif;
        if(cur>s) s++;
        else if(cur<0) cur=0, s++;
    }
    cout << pos%m;
}
    

• 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: 5 / 5
• Subtask 23: 0 / 5