oj.uz

Submission #51452

# Submission time Handle Problem Language Result Execution time Memory
51452 2018-06-18T03:06:36 Z mergesort Watching (JOI13_watching) C++14
0 / 100
 3 ms 636 KB 
#include<bits/stdc++.h>
using namespace std;
int a[4005],n,p,q;

bool check(int w)
{
    int use_1=p,use_2=q,cur_pos=1;
    int len1=w-1,len2=2*w-1;
    while(cur_pos<=n){
        int j=0,x=0,y=0,k=0;
        while(a[cur_pos]+len2>=a[cur_pos+j] && cur_pos+j<=n && use_2){
            x++;
            j++;
        }
        while(a[cur_pos]+len1>=a[cur_pos+k]&& cur_pos+k<=n && use_1){
            y++;
            k++;
        }
        if(x>y && use_2){
            use_2--;
            cur_pos=cur_pos+j;
        }
        else{
            if(use_1){
               use_1--;
               cur_pos=cur_pos+k;
            }
        }
        if(!use_1 && !use_2 && cur_pos<=n ){
            return false;
        }
    }
    if(use_1>=0 && use_2>=0)return true;
    else return false;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>p>>q;
    for(int i=1 ;i<=n;++i)cin>>a[i];
    sort(a+1,a+1+n);
    if(p+q>=n){
        cout<<"1";
        return 0;
    }
    int l=0,r=1e9;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    int ans=1e9;
    if(check(r))ans=min(ans,r);
    if(check(l))ans=min(ans,l);
    cout<<ans;
}

Subtask #1
0 / 50.0

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

Subtask #2
0 / 50.0

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