Submission #1036537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036537		model_code	Sprinklers (CEOI24_sprinklers)	C++17	100 / 100	385 ms	26768 KiB

Main

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

using namespace std;

constexpr int DP_RANGE = 3;
constexpr int DP_SIZE = 1 << (2 * DP_RANGE);

void dp(int N, int M, const vector<int>& s, const vector<int>& f) {
    vector<int> dir(N, -1);
    int K = 0;

    vector<int> dp(DP_SIZE + M*DP_SIZE, -1);
    auto DP = [&] (int fi, int conf) -> int& {
        return dp[DP_SIZE + fi * DP_SIZE + conf];
    };

    auto COVER = [&] (int fi, int si, int conf) {
        int k = 0x7fffffff;
        if (si >= 0 && s[si] == f[fi]) return 0;
        for (int j = 0; j < DP_RANGE; j++) {
            int i = si-DP_RANGE+1 + j;
            if (i >= 0 && (conf & (1 << j)) != 0) {
                k = min(k, f[fi] - s[i]);
            }
        }
        for (int j = DP_RANGE; j < 2*DP_RANGE; j++) {
            int i = si-DP_RANGE+1 + j;
            if (i < N && (conf & (1 << j)) == 0) {
                k = min(k, s[i] - f[fi]);
            }
        }
        return k;
    };

    auto DO_COVER = [&] (int fi, int si, int conf) {
        for (int j = 0; j < 2*DP_RANGE; j++) {
            int i = si-DP_RANGE+1 + j;
            if (0 <= i && i < N) {
                if (dir[i] != -1 && (dir[i] == 0) != ((conf & (1 << j)) == 0)) {
                    cerr << "Bad cover " << i << " " << s[i] << endl;
                }
                dir[i] = conf & (1 << j);
            }
        }
    };

    auto PREV = [&] (int fi, int ds, int conf) {
        if (!ds) return DP(fi-1, conf);
        int k = 0x7fffffff;
        for (int c = 0; c < DP_SIZE; c++) {
            if (ds > 2*DP_RANGE || (c >> ds) == (conf & ((DP_SIZE-1) >> ds))) {
                k = min(k, DP(fi-1, c));
            }
        }
        return k;
    };

    for (int fi = 0, si = -1, psi = -1; fi < M; fi++) {
        while (si + 1 < N && s[si+1] <= f[fi]) si++;
        for (int conf = 0; conf < DP_SIZE; conf++) {
            DP(fi, conf) = COVER(fi, si, conf);
            DP(fi, conf) = max(DP(fi, conf), PREV(fi, si - psi, conf));
        }
        psi = si;
    }

    for (int fi = M, si = N-1, c=0, cm=0; fi-- > 0;) {
        while (si >= 0 && s[si] > f[fi]) {
            si--;
            c <<= 1;
            cm &= cm - 1;
        }
        int minK = 0x7fffffff, minC = 0;
        for (int conf = 0; conf < DP_SIZE; conf++) {
            if ((conf & cm) == (c & cm)) {
                if (DP(fi, conf) < minK) {
                    minK = DP(fi, conf);
                    minC = conf;
                }
            }
        }
        DO_COVER(fi, si, minC);
        c = minC;
        cm = DP_SIZE-1;
        K = max(K, minK);
    }

    if (K == 0x7fffffff) {
        cout << -1 << endl;
        return;
    }

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

int main() {
    int N, M;
    cin >> N >> M;

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

    dp(N, M, s, f);

    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