oj.uz

Submission #666920

# Submission time Handle Problem Language Result Execution time Memory
666920 2022-11-29T22:28:43 Z divad Watching (JOI13_watching) C++14
0 / 100
 2 ms 320 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 224 KB Output is correct
6 Correct 2 ms 216 KB Output is correct
7 Incorrect 2 ms 320 KB Output isn't correct
8 Halted 0 ms 0 KB -