Submission #1084237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084237		farica	Sprinklers (CEOI24_sprinklers)	C++14	0 / 100	10 ms	3420 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 2e5 + 5;

void solve() {
    int n, m;
    cin >> n >> m;
    int s[n+1], f[m], a[n+1];
    for(int i=0; i<n; ++i) cin >> s[i];
    for(int i=0; i<m; ++i) cin >> f[i];
    int cnt = 0;
    for(int i=0; i<=n; ++i) {
        while(cnt<m && f[cnt] <= s[i]) ++cnt;
        a[i] = cnt;
    }
    s[n] = INT_MAX;
    vector<vector<int>>dp(n+1, vector<int>(3, INT_MAX)); // 0 - R, 1 - RL, 2 - RLL
    vector<vector<int>>dp2(n+1, vector<int>(3, 0));
    if(!a[0]) dp[0][0] = dp[0][1] = dp[0][2] = 0;
    else dp[0][1] = dp[0][2] = abs(s[0]-f[0]);
    for(int i=1; i<=n; ++i) {
        int cnt = dp[i-1][0];
        if(a[i]) cnt = max(cnt, abs(s[i-1] - f[a[i]-1]));
        if(dp[i][0] >= cnt) dp[i][0] = cnt, dp2[i][0] = 0;
        cnt = dp[i-1][1];
        if(i >= 2 && a[i] && a[i-1] != a[i]) {
            cnt = max(cnt, abs(s[i-2] - f[a[i]-1]));
            if(dp[i][0] >= cnt) dp[i][0] = cnt, dp2[i][0] = 1;
        } else if(a[i-1] == a[i]) {
            if(dp[i][0] >= cnt) dp[i][0] = cnt, dp2[i][0] = 1;
        }
        cnt = dp[i-1][0];
        int pos = upper_bound(f, f+m, s[i-1] + dp[i-1][0]) - f;
        if(pos != m) cnt = max(cnt, s[i] - f[pos]);
        if(dp[i][1] >= cnt) dp[i][1] = cnt, dp2[i][1] = 0;
        cnt = dp[i-1][1];
        if(i>=2) {
            int pos = upper_bound(f, f+m, s[i-2] + dp[i-1][1]) - f;
            pos = max(pos, a[i-1]);
            if(pos != m) cnt = max(cnt, abs(s[i] - f[pos]));
        }
        if(dp[i][2] >= cnt) dp[i][2] = cnt, dp2[i][2] = 1;
    }
    int ans = dp[n][0];
    if(ans == INT_MAX) ans = -1;
    cout << ans << endl;
    if(ans == -1) return;
    string S = "";
    int tmp = dp2[n][0];
    for(int i=n-1; i>=0; --i) {
        if(!tmp) S += 'R';
        else S += 'L';
        tmp = dp2[i][tmp];
    }
    reverse(S.begin(), S.end());
    cout << S << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

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