oj.uz

Submission #637915

# Submission time Handle Problem Language Result Execution time Memory
637915 2022-09-03T15:02:40 Z tvladm2009 Watching (JOI13_watching) C++14
100 / 100
 130 ms 16016 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAX_N = 2 * 1e3;

int a[MAX_N + 1];
int dp[MAX_N + 1][MAX_N + 1];

int n, p, q;

bool check(int guess) {
    memset(dp, 0, sizeof(dp));
    int j = 1, k = 1;
    for (int i = 1; i <= n; i++) {
        while (a[i] - a[j] >= guess) {
            j++;
        }
        while (a[i] - a[k] >= 2 * guess) {
            k++;
        }
        for (int l = 0; l <= min(i, p); l++) {
            dp[i][l] = dp[k - 1][l] + 1;
            if (l != 0) {
                dp[i][l] = min(dp[i][l], dp[j - 1][l - 1]);
            }
        }
    }
    return (dp[n][min(n, p)] <= q);
}

int cb() {
    int l = 1, r = 1e9, sol = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            sol = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return sol;
}

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

    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);

    int ans = cb();
    cout << ans;

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15956 KB Output is correct
2 Correct 59 ms 15972 KB Output is correct
3 Correct 52 ms 15956 KB Output is correct
4 Correct 51 ms 15976 KB Output is correct
5 Correct 53 ms 15976 KB Output is correct
6 Correct 53 ms 15972 KB Output is correct
7 Correct 55 ms 15972 KB Output is correct
8 Correct 53 ms 15988 KB Output is correct
9 Correct 52 ms 15980 KB Output is correct
10 Correct 52 ms 15960 KB Output is correct
11 Correct 54 ms 15956 KB Output is correct
12 Correct 56 ms 15956 KB Output is correct
13 Correct 56 ms 15976 KB Output is correct
14 Correct 51 ms 15976 KB Output is correct
15 Correct 51 ms 15888 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15956 KB Output is correct
2 Correct 50 ms 15972 KB Output is correct
3 Correct 116 ms 16016 KB Output is correct
4 Correct 128 ms 15956 KB Output is correct
5 Correct 59 ms 15996 KB Output is correct
6 Correct 118 ms 16000 KB Output is correct
7 Correct 54 ms 16000 KB Output is correct
8 Correct 64 ms 15996 KB Output is correct
9 Correct 100 ms 16012 KB Output is correct
10 Correct 130 ms 16004 KB Output is correct
11 Correct 61 ms 15956 KB Output is correct
12 Correct 104 ms 16004 KB Output is correct
13 Correct 55 ms 16008 KB Output is correct
14 Correct 58 ms 16004 KB Output is correct
15 Correct 56 ms 15956 KB Output is correct