Submission #1307794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307794		exoworldgd	Watching (JOI13_watching)	C++20	100 / 100	133 ms	31856 KiB

watching

#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math,omit-frame-pointer")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const int N=2005,inf=1e18;
int n,p,q,a[N],dp[N][N],lo=1,hi=1e9,ans,mid;
bool check(int w){
    for(int i=0;i<=n;i++)for(int j=0;j<=p;j++)dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=1,l,r;i<=n;i++){
        l=upper_bound(a+1,a+n+1,a[i]-w)-a-1,r=upper_bound(a+1,a+n+1,a[i]-2*w)-a-1,dp[i][0]=dp[r][0]+1;
        for(int j=1;j<=min(i,p);j++)dp[i][j]=dp[i][j-1],dp[i][j]=min(dp[i][j],dp[l][j-1]),dp[i][j]=min(dp[i][j],dp[r][j]+1);
    }
    return dp[n][p]<=q;
}
signed main(void){
    exoworldgd;
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1),ans=hi;
    if(p>=n||q>=n)return cout<<1,0;
    while(lo<=hi)mid=(lo+hi)>>1,check(mid)?(ans=mid,hi=mid-1):lo=mid+1;
    cout<<ans;
}

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