Submission #666920

#	Time	Username	Problem	Language	Result	Execution time	Memory
666920		divad	Watching (JOI13_watching)	C++14	0 / 100	2 ms	320 KiB

watching

#include <iostream>
#include <algorithm>
#define MAX 2002
using namespace std;
int n,p,q,a[MAX];

bool check(int w){
    int cap = a[1]+w-1;
    int nrp = 1, nrq = 0;
    for(int i = 2; i <= n; i++){
        if(a[i] <= cap){
            continue;
        }else{
            if(nrp < p){
                cap = a[i]+w-1;
                nrp++;
            }else{
                if(nrq < q){
                    cap = a[i]+2*w-1;
                    nrq++;
                }else{
                    return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int st = 1, dr = a[n];
    int ans = 0;
    /// 0 0 0 0 1 1 1 1 1
    ///         ^
    while(st <= dr){
        int mid = (st+dr)/2;
        if(check(mid)){
            ans = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    cout << ans;
    return 0;
}

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