Submission #51452

#	Time	Username	Problem	Language	Result	Execution time	Memory
51452		mergesort	Watching (JOI13_watching)	C++14	0 / 100	3 ms	636 KiB

watching

#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
• Subtask 2: 0 / 50