Submission #1147177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147177		_8_8_	Sprinklers (CEOI24_sprinklers)	C++20	3 / 100	222 ms	1224 KiB

Main

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

const int  N = (int)1e6 + 12, MOD = 998244353, inf = (int)1e9;

int n, m, s[N], f[N], dp[N][2][2], prv[N][2][2];
char res[N];
int calc(int l, int r) {
    if(l > r) return 0;
    int it = lower_bound(f + 1, f + m + 1, l) - f;
    int it1 = upper_bound(f + 1, f + m + 1, r) - f;
    return it1 - it;
}
bool check(int k) {
    for(int i = 0; i <= n; i++) {
        for(int x = 0; x < 2; x++) {
            for(int y = 0; y < 2; y++) {
                dp[i][x][y] = 0;
            }
        }
    }
    // 0 - left, 1 - right
    dp[1][0][0] = calc(s[1] - k, s[1]);
    dp[1][1][0] = calc(s[1] - k, s[1]);
    dp[1][0][1] = dp[1][1][1] = calc(s[1], s[1]);
    for(int i = 2; i <= n; i++) {
        for(int x = 0; x < 2; x++) {
            for(int y = 0; y < 2; y++) {
                // zyx
                for(int z = 0; z < 2; z++) {
                    int r = s[i - 1];
                    if(y) r = s[i - 1] + k;
                    else if(z) r = max(s[i - 1], s[i - 2] + k);
                    r = min(r, s[i]);
                    int val = dp[i - 1][z][y] + calc(s[i - 1] + 1, r);  
                    if(!x) {
                        val += calc(max(r + 1,s[i] - k), s[i]);
                    }
                    if(!x && y) {
                        if(s[i] - k < s[i - 1]) {
                            if(!z) {
                                val += calc(max(s[i - 2] + 1, s[i] - k), s[i - 1] - 1);
                            } else {
                                if(s[i] - k <= s[i - 2]) {
                                    continue;   
                                } 
                                val += calc(max(s[i - 2] + k + 1, s[i] - k), s[i - 1] - 1);
                            }
                        }
                    }
                    if(val > dp[i][y][x]) {
                        dp[i][y][x] = val;
                        prv[i][y][x] = z;
                    }
                }
            }
        }
    }
    if(max(dp[n][0][0], dp[n][1][0]) < m) return false;
    int x, y;
    if(dp[n][0][0] == m) {
        x = 0, y = 0;
    } else {
        y = 1, x = 0;
    }
    for(int i = n; i >= 1; i--) {
        if(x) res[i] = 'R';
        else res[i] = 'L';
        int bf = y;
        y = prv[i][y][x];
        x = bf;
    }
    return true;
}
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    s[++n] = inf * 2;
    s[0] = -(inf * 2);
    for(int i = 1; i <= m; i++) {
        cin >> f[i];
    }
    int l = -1, r = inf + 1, ans = -1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            r = mid;
            ans = mid;
        } else {
            l = mid;
        }
    }
    if(ans == -1) {
        cout << ans << '\n';
        return;
    }
    check(ans);
    cout << ans << '\n';
    for(int i = 1; i < n; i++) {
        cout << res[i];
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}      

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