Submission #968626

#	Time	Username	Problem	Language	Result	Execution time	Memory
968626		vjudge1	Watching (JOI13_watching)	C++17	100 / 100	192 ms	16424 KiB

watching

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2000;
const int MAXA = 1e9;
const int INF = 1e9;

int N, P, Q;
int A[MAXN + 5];
int nextP[MAXN + 5], nextQ[MAXN + 5];
int DP[MAXN + 5][MAXN + 5];

int f(int idx, int p) {
    if (p < 0) return INF;
    if (idx == N) return 0;
    int &ret = DP[idx][p];
    if (ret != -1) return ret;
    return ret = min(f(nextP[idx], p - 1), f(nextQ[idx], p) + 1);
}

bool valid(int w) {
    for (int i = 0; i < N; i++) {
        nextP[i] = nextQ[i] = N;
        for (int j = i + 1; j < N; j++) {
            if (A[j] - A[i] + 1 > w) {
                nextP[i] = j;
                break;
            }
        }
        for (int j = i + 1; j < N; j++) {
            if (A[j] - A[i] + 1 > 2 * w) {
                nextQ[i] = j;
                break;
            }
        }
    }
    memset(DP, -1, sizeof DP);
    return f(0, P) <= Q;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> P >> Q;
    for (int i = 0; i < N; i++) cin >> A[i];
    if (P + Q >= N) {
        cout << 1 << endl;
        return 0;
    }
    sort(A, A + N);
    int l = 1, r = MAXA, ans = INF, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if (valid(mid)) {
            ans = min(ans, mid);
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << endl;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50