oj.uz

Submission #145124

# Submission time Handle Problem Language Result Execution time Memory
145124 2019-08-18T20:38:31 Z solimm4sks Watching (JOI13_watching) C++14
0 / 100
 10 ms 552 KB 
#include <bits/stdc++.h>
using namespace std;

long long n, p, q;
long long a[200005];

bool check(long long w){

    long long smallCam = p;
    long long bigCam = q;
    for(long long i = 0; i < n; ++i){
        long long ind1 = upper_bound(a, a + n, a[i] + w - 1) - a;
        long long ind2 = upper_bound(a, a + n, a[i] + 2 * w - 1) - a;

        if(ind2 > ind1){
            if(bigCam){
                bigCam--;
                i = ind2 - 1;
                continue;
            }
        }

        if(smallCam){
            smallCam--;
            i = ind1 - 1;
        }else if(bigCam){
            bigCam--;
            i = ind2 - 1;
        }else{
            return false;
        }
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> p >> q;
    for(long long i = 0; i < n; ++i){
        cin >> a[i];
    }

    sort(a, a + n);

    long long l = 0;
    long long r = 100000000000000000;
    long long lc = -1;
    while(l <= r){
        long long mid = (l + r) / 2;
        bool ch = check(mid);
        if(ch){
            r = mid - 1;
            lc = mid;
        }else{
            l = mid + 1;
        }
    }

  if(lc == -1){
    while(1);
  }
  
    cout << lc << "\n";
    return 0;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 8 ms 552 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -