제출 #1277781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277781		nmdk	Watching (JOI13_watching)	C++20	0 / 100	175 ms	16692 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n, p, q, a[N], f[N][N];
int tk(int d, int c, int k){
    int ans=-1;
    while (d<=c){
        int g=(d+c)/2;
        if (a[g]>=k){
            ans=g;
            c=g-1;
        } else d=g+1;
    }
    return ans;
}
int check(int i, int cn, int cl, int w){
    if (cn < 0 || cl < 0) return 0;
    if (i==-1) return 1;
    int &res = f[cn][cl];
    if (res!=-1) return res;
    res = 0;
    if (check(tk(1, n, a[i]+w), cn-1, cl, w)==1) return res=1;
    if (check(tk(1, n, a[i]+2*w), cn, cl-1, w)==1) return res=1;
    return res;
}
int solve(int d, int c){
    int ans=-1;
    while (d<=c){
        int g=(d+c)/2;
        memset(f, -1, sizeof(f));
        if (check(1, p, q, g)){
            ans=g;
            c=g-1;
        } else d=g+1;
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> p >> q;
    q=min(q, n);
    p=min(p, n);
    for (int i=1; i<=n; ++i) cin >> a[i];
    sort (a+1, a+n+1);
    cout << solve(0, 1e9);
}

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