Submission #492879

#	Time	Username	Problem	Language	Result	Execution time	Memory
492879		alextodoran	Watching (JOI13_watching)	C++17	100 / 100	83 ms	14132 KiB

watching

/**
 ____ ____ ____ ____ ____
||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 / 50
• Subtask 2: 50 / 50