Submission #1192543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192543		prideliqueee	Watching (JOI13_watching)	C++20	50 / 100	1093 ms	328 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int a[2010];
int n,p,q;
int b;
pair<int,int> mx[2010];
void check(int i,int pp,int qq,int w)
{
    if(b)
    return;
    if(n-i<=pp+qq)
    {
        b=1;
        return;
    }
    if(i>=n)
    return;
    int ppp=mx[i].f,qqq=mx[i].s;
    if(ppp>=pp&&qqq>=qq)
    return;
    if(ppp+qqq>=pp+qq&&qqq>=qq)
    return;
    mx[i]={pp,qq};
    int val=a[i];
    int d1=lower_bound(a,a+n,val+w)-a;
    int d2=lower_bound(a,a+n,val+w*2)-a;
    if(pp>0)
    {
        if(d1>=n)
        {
            b=1;
            return;
        }
        check(d1,pp-1,qq,w);
    }
    if(qq>0&&!(pp>0&&d1==d2))
    {
        if(d2>=n)
        {
            b=1;
            return;
        }
        check(d2,pp,qq-1,w);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>p>>q;
    memset(a,127,sizeof a);
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    int l=1,r=a[n-1]-a[0]+1;
    while(l<r)
    {
        int mid=(l+r)/2;
        b=0;
        for(int i=0;i<n;i++)
        mx[i]={0,0};
        check(0,p,q,mid);
        if(b)
        r=mid;
        else
        l=mid+1;
    }
    cout<<l;
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50