Submission #511049

#	Time	Username	Problem	Language	Result	Execution time	Memory
511049		CyberSleeper	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	300 ms	2384 KiB

linear_garden

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const int MX=1000005, MOD=998244353, BLOCK=327, INF=1e9+7;
const ll INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

int N, M, DP[2][2][5][5]; //idx, higher, lowest, highest
string S, A="LP";

void reset(int idx){
    for(int i=0; i<2; i++)
        for(int j=0; j<5; j++)
            for(int k=0; k<5; k++)
                DP[idx][i][j][k]=0;
}

int main(){
    fastio;
    cin >> N >> M >> S;
    S=" "+S;
    DP[0][1][2][2]=1;
    for(int i=1, now, bef; i<=N; i++){
        now=i%2, bef=now^1;
        reset(now);
        for(int k=0; k<5; k++){
            for(int l=0; l<5; l++){
                for(int j=0, low, high; j<2; j++){
                    if(!j)
                        low=min(k-1, 1), high=max(l-1, 1);
                    else
                        low=min(k+1, 3), high=max(l+1, 3);
                    if(low<0 || 4<high)
                        continue;

                    DP[now][0][low][high]+=DP[bef][0][k][l];
                    if(DP[now][0][low][high] >= M)
                        DP[now][0][low][high]-=M;

                    if(A[j]<S[i])
                        DP[now][0][low][high]+=DP[bef][1][k][l];
                    else if(A[j]==S[i])
                        DP[now][1][low][high]+=DP[bef][1][k][l];

                    if(DP[now][0][low][high] >= M)
                        DP[now][0][low][high]-=M;
                    if(DP[now][1][low][high] >= M)
                        DP[now][1][low][high]-=M;
                }
            }
        }
    }
    int ans=1;

    for(int i=0; i<5; i++){
        for(int j=i; j<5; j++){
            ans+=DP[N%2][0][i][j];
            if(ans >= M)
                ans-=M;
        }
    }
    cout << ans << nl;
}

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