oj.uz

Submission #824158

# Submission time Handle Problem Language Result Execution time Memory
824158 2023-08-13T16:04:14 Z Koyote Watching (JOI13_watching) C++14
100 / 100
 231 ms 16008 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 2;
int n, p, q, a[N];
int dp[N][N]; // dp[i][j]: number of small cameras needed to take pictures of i events with j big cameras

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    if (p + q >= n) return cout << 1 << '\n', 0;

    auto binary_func = [&](int x) {
        memset(dp, 0x7f, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            int sl = 1, bl = 1;
            while (a[i] - a[sl] + 1 > x) sl++;
            while (a[i] - a[bl] + 1 > 2 * x) bl++;
            for (int j = 0; j <= q; j++) {
                dp[i][j] = dp[sl - 1][j] + 1;
                if (j > 0) dp[i][j] = min(dp[i][j], dp[bl - 1][j - 1]);
            }
        }
        for (int j = 0; j <= q; j++) if (dp[n][j] <= p) return true;
        return false;
    };

    int lo = 1, hi = int(1e9), ans = int(1e9);
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (binary_func(mid)) ans = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout << ans << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16008 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 26 ms 16008 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 30 ms 16008 KB Output is correct
8 Correct 28 ms 15956 KB Output is correct
9 Correct 30 ms 16004 KB Output is correct
10 Correct 28 ms 16008 KB Output is correct
11 Correct 24 ms 16008 KB Output is correct
12 Correct 24 ms 16008 KB Output is correct
13 Correct 28 ms 15956 KB Output is correct
14 Correct 24 ms 16008 KB Output is correct
15 Correct 24 ms 16004 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16008 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 105 ms 15992 KB Output is correct
8 Correct 133 ms 15996 KB Output is correct
9 Correct 102 ms 15996 KB Output is correct
10 Correct 91 ms 15996 KB Output is correct
11 Correct 231 ms 16000 KB Output is correct
12 Correct 185 ms 15992 KB Output is correct
13 Correct 86 ms 16004 KB Output is correct
14 Correct 86 ms 15992 KB Output is correct
15 Correct 82 ms 15956 KB Output is correct