제출 #1257040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257040		inkvizytor	Watching (JOI13_watching)	C++20	100 / 100	111 ms	16232 KiB

watching

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

#define ll long long

vector<vector<int>> dp (2000, vector<int> (2000, -1));

bool check(int n, int p, int q, vector<ll> &a, int w) {
    vector<ll> x (n+1, n), y (n+1, n);
    int b = 0, e = 0;
    while (b < n) {
        if (a[e]-a[b]+1 <= w) {
            e++;
        }
        else {
            x[b] = e;
            b++;
        }
    }
    b = 0, e = 0;
    while (b < n) {
        if (a[e]-a[b]+1 <= 2*w) {
            e++;
        }
        else {
            y[b] = e;
            b++;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= p; i++) {
        dp[i][0] = x[dp[i-1][0]];
    }
    for (int i = 1; i <= q; i++) {
        dp[0][i] = y[dp[0][i-1]];
    }
    for (int i = 1; i <= p; i++) {
        for (int j = 1; j <= q; j++) {
            dp[i][j] = max(x[dp[i-1][j]], y[dp[i][j-1]]);
        }
    }
    return (dp[p][q] == n);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, p, q;
    cin >> n >> p >> q;
    vector<ll> a (n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    a.push_back(1e12);
    if (p+q >= n) {
        cout << 1 << '\n';
        return 0;
    }
    int pow = 1<<30;
    int w = 0;
    while (pow > 0) {
        w += pow;
        if (check(n, p, q, a, w)) {
            w -= pow;
        }
        pow /= 2;
    }
    cout << w+1 << '\n';
}

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