oj.uz

Submission #1084003

# Submission time Handle Problem Language Result Execution time Memory
1084003 2024-09-04T19:05:37 Z farica Sprinklers (CEOI24_sprinklers) C++14
0 / 100
 9 ms 3420 KB 
#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, abs(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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 7 ms 1884 KB Correct
3 Incorrect 0 ms 456 KB User solution is incorrect
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 8 ms 2140 KB Correct
3 Incorrect 3 ms 1880 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Incorrect 0 ms 344 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Incorrect 9 ms 3420 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 348 KB Correct
3 Correct 7 ms 1884 KB Correct
4 Incorrect 0 ms 456 KB User solution is incorrect
5 Halted 0 ms 0 KB -