제출 #974844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974844		vjudge1	구경하기 (JOI13_watching)	C++14	100 / 100	220 ms	16544 KiB

watching

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

const int N = 2000;
const int A = 1e9;
const int INF = 1e9;

int n, p, q;
int a[N + 5];
int nextP[N + 5], nextQ[N + 5];
int memo[N + 5][N + 5];

int dp(int idx, int p) {
    if (p < 0) return INF;
    if (idx >= n) return 0;
    
    int &ret = memo[idx][p];
    if (memo[idx][p] != -1) return ret;
    

    ret = min(dp(nextP[idx], p - 1), dp(nextQ[idx], p) + 1);   
    return ret;
}

bool solve(int w) {
    int j = 1, k = 1;
    for(int i = 0; i < n; i++){
        while(j < n && a[j] - a[i] + 1 <= w) j++;
        while(k < n && a[k] - a[i] + 1 <= 2*w) k++;
        nextP[i] = j;
        nextQ[i] = k;
    }
 
    memset(memo, -1, sizeof(memo));
    return dp(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 << "\n";
        return 0;
    }

    sort(a, a + n);

    int l = 1, r = A, ans = INF;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (solve(mid)) {
            ans = min(ans, mid);
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

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