oj.uz

Submission #492879

# Submission time Handle Problem Language Result Execution time Memory
492879 2021-12-09T13:09:21 Z alextodoran Watching (JOI13_watching) C++17
100 / 100
 83 ms 14132 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 2000;

int N, P, Q;

int A[N_MAX + 2];

int dp[N_MAX + 2][N_MAX + 2];

bool solve (int w) {
    int jp = 0, jq = 0;
    for (int i = 1; i <= N; i++) {
        while (A[i] - A[jp] + 1 > w) {
            jp++;
        }
        while (A[i] - A[jq] + 1 > w * 2) {
            jq++;
        }
        for (int cntp = 0; cntp <= min(i, P); cntp++) {
            /// Use a large camera (Q)
            dp[i][cntp] = dp[jq - 1][cntp] + 1;
            /// Use a small camera (P)
            if (cntp > 0) {
                dp[i][cntp] = min(dp[i][cntp], dp[jp - 1][cntp - 1]);
            }
        }
    }
    for (int cntp = 0; cntp <= min(N, P); cntp++) {
        if (dp[N][cntp] <= Q) {
            return true;
        }
    }
    return false;
}

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 l = 1, r = (int) 1e9;
    while (l < r) {
        int mid = (l + r) / 2;
        if (solve(mid) == true) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << l << "\n";

    return 0;
}

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 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 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 5 ms 8268 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 73 ms 14132 KB Output is correct
4 Correct 76 ms 14132 KB Output is correct
5 Correct 11 ms 8956 KB Output is correct
6 Correct 83 ms 14028 KB Output is correct
7 Correct 5 ms 8420 KB Output is correct
8 Correct 12 ms 9312 KB Output is correct
9 Correct 49 ms 13064 KB Output is correct
10 Correct 75 ms 14024 KB Output is correct
11 Correct 10 ms 9036 KB Output is correct
12 Correct 58 ms 14028 KB Output is correct
13 Correct 5 ms 8396 KB Output is correct
14 Correct 5 ms 8396 KB Output is correct
15 Correct 6 ms 8396 KB Output is correct