제출 #511036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511036		CyberSleeper	Linear Garden (IOI08_linear_garden)	C++14	75 / 100	132 ms	65540 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[MX][2][5][5]; //idx, higher, lowest, highest
string S, A="LP";

int main(){
    fastio;
    cin >> N >> M >> S;
    S=" "+S;
    DP[0][1][2][2]=1;
    for(int i=1; i<=N; i++){
        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[i][0][low][high]+=DP[i-1][0][k][l];
                    if(A[j]<S[i]){
                        DP[i][0][low][high]+=DP[i-1][1][k][l];
                    }else if(A[j]==S[i]){
                        DP[i][1][low][high]+=DP[i-1][1][k][l];
                    }
                    if(DP[i][0][low][high] > M)
                        DP[i][0][low][high]-=M;
                    if(DP[i][1][low][high] > M)
                        DP[i][1][low][high]-=M;
                }
            }
        }
    }
    int ans=1;

    for(int i=0; i<5; i++){
        for(int j=i; j<5; j++){
            ans+=DP[N][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: 0 / 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: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5