제출 #461988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
461988		nickyrio	Watching (JOI13_watching)	C++17	50 / 100	1076 ms	16332 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int N = 2020;
int n, p, q, a[N];

int dp[N][N];
void Max(int &a, int b) { a = (a < b ? b : a); }

bool Check(int w) {
    memset(dp, 0, sizeof dp);
    int total = min(n, p + q);
    for (int i = 0; i < total; ++i) {
        for (int np = 0; np <= min(i, p); ++np) {
            int x = dp[i][np];
            int nq = i - np;
            if (x == n) {
                return true;
            }
            if (np < p) {
                int nxt = lower_bound(a, a + n, a[x] + w) - a;
                Max(dp[i + 1][np + 1], nxt);
            }
            if (nq < q) {
                int nxt = lower_bound(a, a + n, a[x] + w + w) - a;
                Max(dp[i + 1][np], nxt);
            }
        }
    }
    return dp[total][p] >= n;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> p >> q;
    p = min(p, n), q = min(q, n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int l = 0, r = 1e9, cur = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (Check(mid)) {
            cur = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << cur << '\n';
}

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