Submission #775518

#	Time	Username	Problem	Language	Result	Execution time	Memory
775518		kirakaminski968	Watching (JOI13_watching)	C++17	100 / 100	581 ms	16056 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int N,P,Q,A[2005],sec1[2005],sec2[2005],dp[2005][2005];
bool check(int w){
    for(int i = 0;i<N;++i){
        sec1[i] = (int)(lower_bound(A,A+N,A[i]+w)-A);
        sec2[i] = (int)(lower_bound(A,A+N,A[i]+2*w)-A);
    }
    sec1[N] = sec2[N] = N;
    for(int i = P;i>=0;--i){
        for(int j = Q;j>=0;--j){
            if(i == P && j == Q) continue;
            int cur = 0;
            if(i != P) cur = max(cur,sec1[dp[i+1][j]]);
            if(j != Q) cur = max(cur,sec2[dp[i][j+1]]);
            dp[i][j] = cur;
        }
    }
    return dp[0][0] >= N;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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 lo = 0, hi = 500000000;
    while(lo < hi){
        int mid = (lo+hi)/2;
        if(check(mid)){
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
    cout << lo << "\n";
    return 0;
}

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