Submission #1251818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251818		efex12	Watching (JOI13_watching)	C++20	50 / 100	445 ms	327680 KiB

watching

#include<bits/stdc++.h>
#define int long long
#define pint pair<int,int>
#define N 2055
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define INF 1000000005
#define pu push
 
using namespace std;

int n,a,b;
int arr[N],num;
int dp[N][N];
pint go[N];

inline int f(int ind,int x)
{
    if(x<0)
        return INF;
    if(ind==n)
        return 0;
    if(dp[ind][x]!=-1)
        return dp[ind][x];
    return dp[ind][x]=min(f(go[ind].ff,x-1),f(go[ind].ss,x)+1);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>a>>b;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    if((a+b)>=n)
    {
        cout<<"1\n";
        return 0;
    }
    int l=0,r=1000000002/(a+b)+100;
    int ans=r;
    while(l<=r)
    {
        memset(dp,-1,sizeof(dp));
        memset(go,0,sizeof(go));
        int mid=(l+r)/2;
        num=mid;
        int x=0,y=0;
        for(int i=0;i<n;i++)
        {
            while(x<n&&(arr[i]+num)>arr[x])
                x++;
            while(y<n&&(arr[i]+2*num)>arr[y])
                y++;
            //cout<<x<<" "<<y<<endl;
            go[i]={x,y};
        }
        if(f(0,a)<=b)
        {
            ans=min(ans,mid);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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