oj.uz

Submission #462099

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

using namespace std;

const int N = 2020;
int n, p, q;
long long a[N];
int dp[N][N];
void Min(int &a, int b) { a = (a > b ? b : a); }

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 dp[n][p] <= q;
    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 1 ms 332 KB Output is correct
3 Correct 1 ms 320 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 708 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 8 ms 8268 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 259 ms 16076 KB Output is correct
4 Correct 347 ms 16196 KB Output is correct
5 Correct 25 ms 8912 KB Output is correct
6 Correct 315 ms 16076 KB Output is correct
7 Correct 12 ms 8476 KB Output is correct
8 Correct 31 ms 9340 KB Output is correct
9 Correct 137 ms 14228 KB Output is correct
10 Correct 301 ms 16148 KB Output is correct
11 Correct 26 ms 9032 KB Output is correct
12 Correct 172 ms 15920 KB Output is correct
13 Correct 15 ms 8396 KB Output is correct
14 Correct 19 ms 8508 KB Output is correct
15 Correct 16 ms 8508 KB Output is correct