Submission #1036544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036544		model_code	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	97 ms	2764 KiB

Main

// Author: Robert Jaworski
#include <bits/stdc++.h>

using namespace std;

int dp(int N, int M, const vector<int>& s, const vector<int>& f, vector<int>& dir) {
    constexpr int DP_R = 0;
    constexpr int DP_LL = 1;
    constexpr int DP_RL = 2;
    constexpr int DP_SIZE = 3;

    vector<int> dp(DP_SIZE * (N + 1)); // min K to water all the plants until s[i]
    auto DP = [&] (int si, int conf) -> decltype(auto) {
        return dp[DP_SIZE + si * DP_SIZE + conf];
    };
    dp[DP_LL] = 0;
    dp[DP_R] = dp[DP_RL] = 0x7fffffff;

    auto WATER = [&] (int siR, int siL, int fi) {
        if (fi < 0) return 0;
        int R = 0 <= siR && siR < N ? f[fi] - s[siR] : 0x7fffffff;
        if (R < 0) R = 0x7fffffff;
        int L = 0 <= siL && siL < N ? s[siL] - f[fi] : 0x7fffffff;
        if (L < 0) L = 0x7fffffff;
        return min(R, L);
    };

    auto CHECK = [&] (int si, int dp1, int dp2, int fi, int pfi, int ppfi) {
        if (dp2 == DP_RL && dp1 != DP_R) return 0x7fffffff;
        if (dp2 == DP_LL && dp1 == DP_R) return 0x7fffffff;
        int k = DP(si-1, dp1);
        int r = dp1 == DP_R ? si-1 : dp1 == DP_RL ? si-2 : dp2 == DP_R ? si : -1;
        int l = dp2 != DP_R ? si : dp1 != DP_R ? si-1 : -1;
        for (int ffi = pfi+1; ffi <= fi; ffi++) {
            if (s[si] != f[ffi]) k = max(k, WATER(r, l, ffi));
        }
        if (dp2 == DP_RL && si-1 >= 0) {
            for (int dp3 = 0; dp3 < DP_SIZE; dp3++) {
                int k2 = DP(si-2, dp3);
                int r2 = dp3 == DP_R ? si-2 : dp3 == DP_RL ? si-3 : -1;
                for (int ffi = ppfi+1; ffi <= fi; ffi++) {
                    if (s[si] != f[ffi]) k2 = max(k2, WATER(r2, l, ffi));
                }
                k = min(k, k2);
            }
        }
        return k;
    };

    int si, fi, pfi, ppfi;
    for (si = 0, fi = pfi = ppfi = -1; si < N; si++) {
        while (fi + 1 < M && f[fi+1] <= s[si]) fi++;
        DP(si, DP_R) = DP(si, DP_LL) = DP(si, DP_RL) = 0x7fffffff;
        for (int dp1 = 0; dp1 < DP_SIZE; dp1++) {
            for (int dp2 = 0; dp2 < DP_SIZE; dp2++) {
                DP(si, dp2) = min(DP(si, dp2), CHECK(si, dp1, dp2, fi, pfi, ppfi));
            }
        }
        ppfi = pfi;
        pfi = fi;
    }

    fi = M - 1;
    int K = 0x7fffffff;
    int choice = -1;
    if (fi == pfi) {
        if (DP(si-1, DP_R) < K) {
            K = DP(si-1, DP_R);
            choice = DP_R;
        }
        if (DP(si-1, DP_RL) < K) {
            K = DP(si-1, DP_RL);
            choice = DP_RL;
        }
        if (DP(si-1, DP_LL) < K) {
            K = DP(si-1, DP_LL);
            choice = DP_LL;
        }
    }
    else {
        if (DP(si-1, DP_R) < K) {
            K = max(DP(si-1, DP_R), WATER(si-1, -1, fi));
            choice = DP_R;
        }
        if (DP(si-1, DP_RL) < K) {
            int k = max(DP(si-1, DP_RL), WATER(si-2, -1, fi));
            if (k < K) {
                K = k;
                choice = DP_RL;
            }
        }
    }

    if (K < 0x7fffffff) {
        dir.resize(N, 0);
        for (si = N; si-- > 0;) {
            switch (choice) {
            case DP_R:
                dir[si] = 1;
                if (DP(si-1, DP_R) <= K) choice = DP_R;
                else if (DP(si-1, DP_RL) <= K) choice = DP_RL;
                else if (DP(si-1, DP_LL) <= K) choice = DP_LL;
                else {
                    cerr << "Bad" << endl;
                }
                break;
            case DP_RL:
                dir[si] = 0;
                choice = DP_R;
                break;
            case DP_LL:
                dir[si] = 0;
                if (DP(si-1, DP_RL) <= K) choice = DP_RL;
                else if (DP(si-1, DP_LL) <= K) choice = DP_LL;
                else {
                    cerr << "Bad" << endl;
                }
                break;
            }
        }
    }

    return K;
}

int main() {
    // freopen("data/inputs/01_right_closed.in", "r", stdin);

    int N, M;
    cin >> N >> M;

    vector<int> s(N, 0);
    vector<int> f(M, 0);
    vector<int> conf;
    for (auto&& x : s) {
        cin >> x;
    }
    for (auto&& x : f) {
        cin >> x;
    }

    if (N == 1) {
        if (s.back() <= f[0]) {
            cout << (f.back() - s.back()) << endl << "R" << endl;
        }
        else if (s[0] >= f.back()) {
            cout << (s[0] - f[0]) << endl << "L" << endl;
        }
        else {
            cout << -1 << endl;
        }
        return 0;
    }

    int K = dp(N, M, s, f, conf);
    if (K == 0x7fffffff) {
        cout << -1 << endl;
        return 0;
    }

    cout << K << endl;
    for (auto&& x : conf) {
        cout << (x ? 'R' : 'L');
    }
    cout << endl;

    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 17 / 17
• Subtask 4: 27 / 27
• Subtask 5: 47 / 47