Submission #163274

#	Time	Username	Problem	Language	Result	Execution time	Memory
163274		aggu_01000101	Watching (JOI13_watching)	C++14	0 / 100	90 ms	508 KiB

watching

#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 = 0;
            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--;
        }
        while(covered>0){
            int left = covered;
            int j = 0;
            for(int i = 0;i<left;i++){
                if(p1==0) goto outer;
                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
• Subtask 2: 0 / 50