oj.uz

Submission #462105

# Submission time Handle Problem Language Result Execution time Memory
462105 2021-08-10T07:56:22 Z nickyrio Watching (JOI13_watching) C++17
100 / 100
 333 ms 16196 KB 
#include <bits/stdc++.h>

using namespace std;

void Min(int &a, int b) { a = (a > b ? b : a); }
const int N = 2020;

int n, p, q, a[N];
int dp[N][N];

bool Check(long long w) {
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= p; ++j) dp[i][j] = 1e9;
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        int nxt_p = lower_bound(a, a + n, a[i] + w) - a;
        int nxt_q = lower_bound(a, a + n, a[i] + w + w) - a;
        for (int np = 0; np <= p; ++np) {
            Min(dp[nxt_p][np + 1], dp[i][np]);
            Min(dp[nxt_q][np], dp[i][np] + 1);
        }
    }
    for (int i = 0; i <= p; ++i) if (dp[n][i] <= q) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> p >> q;
    p = min(p, n), q = min(q, n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int l = 0, r = 1e9, cur = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (Check(mid)) {
            cur = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << cur << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8356 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 297 ms 16124 KB Output is correct
4 Correct 333 ms 16120 KB Output is correct
5 Correct 24 ms 8908 KB Output is correct
6 Correct 314 ms 16196 KB Output is correct
7 Correct 12 ms 8444 KB Output is correct
8 Correct 34 ms 9328 KB Output is correct
9 Correct 141 ms 14204 KB Output is correct
10 Correct 303 ms 16128 KB Output is correct
11 Correct 26 ms 9036 KB Output is correct
12 Correct 175 ms 15988 KB Output is correct
13 Correct 13 ms 8444 KB Output is correct
14 Correct 16 ms 8360 KB Output is correct
15 Correct 17 ms 8476 KB Output is correct