Submission #1275372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275372		cngkhanh_ti22	Linear Garden (IOI08_linear_garden)	C++20	75 / 100	129 ms	131072 KiB

linear_garden

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

// N up to 1,000,000  → we keep L as [N+2][3][3][2]
static long long L[1000002][3][3][2];
static int S[1000002];

long long N, M;

// Recursive function similar to Pascal's Tinh()
long long Tinh(int i, int hl, int hp, int ok) {
    // Already computed → return memoized
    if (L[i][hl][hp][ok] != -1)
        return L[i][hl][hp][ok];

    // Base: past the last position → 1 valid completion
    if (i > N)
        return L[i][hl][hp][ok] = 1 % M;

    long long ans = 0;

    // ----- Try placing 'L' (0) -----
    if (hl < 2) {                                  // cannot exceed balance
        int nextOk = ok | (0 < S[i]);              // becomes 1 if we place smaller than target
        ans = Tinh(i + 1, hl + 1, max(0, hp - 1), nextOk);
    }

    // ----- Try placing 'P' (1) -----
    if ((ok == 1 || S[i] == 1) && hp < 2) {        // allowed only if <= target
        int nextOk = ok | (1 < S[i]);              // actually stays same
        ans += Tinh(i + 1, max(0, hl - 1), hp + 1, nextOk);
    }

    return L[i][hl][hp][ok] = ans % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    string garden;
    cin >> garden;

    // Convert garden letters to 0/1 for easier compare
    for (int i = 1; i <= N; ++i) {
        S[i] = (garden[i - 1] == 'P' ? 1 : 0);
    }

    // Initialize DP array to -1 (uncomputed)
    for (int i = 0; i <= N + 1; ++i)
        for (int hl = 0; hl < 3; ++hl)
            for (int hp = 0; hp < 3; ++hp)
                for (int ok = 0; ok < 2; ++ok)
                    L[i][hl][hp][ok] = -1;

    long long result = Tinh(1, 0, 0, 0);
    result = (result % M + M) % M;     // make sure non-negative
    cout << result << "\n";
    return 0;
}

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