Submission #239185

#	Time	Username	Problem	Language	Result	Execution time	Memory
239185		osaaateiasavtnl	Linear Garden (IOI08_linear_garden)	C++14	96 / 100	845 ms	26004 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int C = 3;
map <int, int> dp[C][C], t[C][C];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, MOD;
    string s;

    cin >> n >> MOD >> s;

    vector <int> mn(n + 1), mx(n + 1), cur(n + 1);

    // L = -1
    // P = 1

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'L')
            cur[i + 1] = cur[i] - 1;
        else
            cur[i + 1] = cur[i] + 1;
        mn[i + 1] = min(mn[i], cur[i + 1]);
        mx[i + 1] = max(mx[i], cur[i + 1]);
    }   

    for (int l = 0; l < C; ++l)
        for (int r = 0; r < C; ++r)
            for (int b = -l; b <= r; ++b)
                dp[l][r][b] = 1;

    vector <int> de = {-1, 1};

    int ans = 1;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == 'P') {
            int cur1 = cur[i] - 1;
            int mn1 = max(-mn[i], -cur1);
            int mx1 = max(mx[i], cur1);
            if (mn1 < C && mx1 < C) {
                ans += dp[mn1][mx1][cur1];
                ans %= MOD;
                //cout << mn1 << ' ' << mx1 << ' ' << cur1 << endl;
                //cout << mn1 << ' ' << mx1 << ' ' << cur1 << " : " << dp[mn1][mx1][cur1] << endl;
            }
        }   
        //cout << "calc" << endl;
        for (int l = 0; l <= 2; ++l) {
            for (int r = 0; r <= 2; ++r) {
                for (int cur = -l; cur <= r; ++cur) {
                    t[l][r][cur] = 0;
                    for (int x : de) {
                        int cur1 = cur + x;
                        int l1 = min(-l, cur1);
                        int r1 = max(r, cur1);
                        if (r1 - l1 <= 2) {

                            /*
                            if (l == 2 && r == 0 && cur == -1) {
                                cout << "add " << -l1 << ' ' << r1 << ' ' << cur1 << " : " << dp[-l1][r1][cur1] << endl;
                            }
                            */  

                            t[l][r][cur] += dp[-l1][r1][cur1];
                            t[l][r][cur] %= MOD;
                        }   
                    }   
                }   
            }   
        }   
        for (int l = 0; l <= 2; ++l) {
            for (int r = 0; r <= 2; ++r) {
                for (int cur = -l; cur <= r; ++cur) {
                    dp[l][r][cur] = t[l][r][cur];
                }   
            }   
        }   
    }   
    cout << ans % MOD << endl;
}

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