oj.uz

Submission #163278

# Submission time Handle Problem Language Result Execution time Memory
163278 2019-11-12T10:31:55 Z aggu_01000101 Watching (JOI13_watching) C++14
0 / 100
 122 ms 408 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int32_t main(){
    int n, p, q;
    cin>>n>>p>>q;
    int a[n];
    for(int i = 0;i<n;i++) cin>>a[i];
    //cout<<"DONE WITH INPUT"<<endl;
    sort(a, a+n);
    int u = 1e9;
    int l = 1;
    int mini = 1e9;
    while(u>=l){
        int m = (l+u)/2;
        //cout<<m<<endl;
        int covered = n;
        int p1 = p, q1 = q;
        int b[n];
        for(int i = 0;i<n;i++) b[i] = a[i];
        while(q1 && covered>0){
            pair<int, int> count = make_pair(0, 0);
            int j = 1;
            for(int i = 0;i<covered;i++){
                while(j<covered && b[j]<(2*m+b[i])) j++;
                if(count.first<(j-i)) count = make_pair(j-i, i);
                i = j-1;
            }
            //cout<<(covered-count.first)<<" ARE STILL LEFT"<<endl;
            for(int i = count.second;(i+count.first)<covered;i++){
                b[i] = b[i+count.first];
            }
            //cout<<"PRINTING ARRAY: ";
            covered-=count.first;
            //for(int i = 0;i<covered;i++) cout<<b[i]<<" ";
            //cout<<endl;
            q1--;
        }

        int left = covered;
        int j = 1;
        for(int i = 0;i<left;i++){
            if(p1==0) goto outer;
            j = max(j, i+1);
            while(j<left && b[j]<(m+b[i])) j++;
            covered-=(j-i);
            i = j-1;
            p1--;
        }
        outer:
        //cout<<l<<" "<<u<<" "<<m<<" "<<covered<<endl;
        if(covered==0){
            u = m-1;
            mini = min(m, mini);
        }
        else{
            l  = m+1;
        }
    }
    cout<<mini<<endl;
}

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 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 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 4 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 106 ms 376 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 117 ms 408 KB Output is correct
6 Correct 122 ms 400 KB Output is correct
7 Incorrect 4 ms 380 KB Output isn't correct
8 Halted 0 ms 0 KB -