Submission #510059

#	Time	Username	Problem	Language	Result	Execution time	Memory
510059		Vegeta10	Watching (JOI13_watching)	C++17	100 / 100	470 ms	31828 KiB

watching

#include<bits/stdc++.h>
#include<fstream>

using namespace std;

//--------------------------Containers------------------------/
typedef     long long int           ll;
typedef     unsigned long long int  ull;
typedef     long double             ld;
typedef     vector < int >          vi;
typedef     vector < ll >           vll;
typedef     vector < vll >          vvll;
typedef     pair< int,int >         pi;
typedef     pair< ll, ll >          pll;
typedef     vector< pi >            vpi;
typedef     vector< pll >           vpll;
//------------------------------------------------------------/

//------------------------typedef int MyCustomType;--Limits & Constants----------------/
#define     MAX                 200007
#define     MOD                 int(1e9 + 7)
#define     mod                 int(1e9 + 7)
#define     INF                 ll(8230219982008199610)
#define     MINF                ll(-8230219982008199610)
#define     IL                  INT_MAX
#define     MIL                 INT_MIN
#define     PI                  2*acos(0.0)
//------------------------------------------------------------/

//--------------------------Macros----------------------------/
#define     fast                ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define     pf                  printf
#define     sc                  scanf
#define     all(a)              (a).begin(),(a).end()
#define     sz(x)               int(x.size())
#define     pb                  push_back
#define     eb                  emplace_back
#define     mp                  make_pair
#define     ff                  first
#define     ss                  second
#define     mem(a,n)            memset(a, n, sizeof(a) )
#define     gcd(a,b)            __gcd(a,b)
#define     lcm(a,b)            (a*(b/gcd(a,b)))
#define     forn(i,n)          for(int i=0; i<n; i++)
#define     loop1(i,n)          for(int i=1; i<=n; i++)
#define     rev0(i,n)           for(int i=n-1; i>=0; i--)
#define     rev1(i,n)           for(int i=n; i>0; i--)
//------------------------------------------------------------/

//----------------------Scans and Prints----------------------/
#define     sc1(x)              scanf("%d",&x)
#define     sc2(x,y)            scanf("%d %d",&x,&y)
#define     sc3(x,y,z)          scanf("%d %d %d",&x,&y,&z)
#define     scd1(x)             scanf("%lld",&x)
#define     scd2(x,y)           scanf("%lld %lld",&x,&y)
#define     pf1(x)              printf("%d\n",x)
#define     pf2(x,y)            printf("%d %d\n",x,y)
#define     pfd1(x)             printf("%lld\n",x)
#define     pfd2(x,y)           printf("%lld %lld\n",x,y)
#define     t_case(t)           for(int cs = 1; cs<=t; cs++)
#define     print(a,n)          for(int pr = 0; pr<int(n); pr++)cout<<a[pr]<<" ";cout<<endl
#define     printa(x)           cout<<x<<endl;
#define     debug               cout<<" OK "<<endl
//------------------------------------------------------------/
ll mul(ll a,ll b){
  return ((a % mod)*(b % mod))%mod;
}
ll add(ll a,ll b){
    return ((a % mod)+(b % mod))%mod;
}
ll sub(ll a,ll b){
    ll ans = ((a%mod) - (b%mod))%mod;
    ans%=mod;
    ans = (ans+mod)%mod;
    return ans;
}
ll mpow(ll a, ll b){
    ll ans = 1;
    ll po = a;
    //b can be written as in binary 2^0 + 2^1+ 2^2+...
    //a^b = a^(2^0 + 2^1+ 2^2+...)
    //a^b = a^(1)*(a^2)*(a^4)*(a^16)...
    while(b!=0){
        if(b%2){
           ans = ((ans%mod)*(po%mod))%mod;
        }
        po = ((po%mod)*(po%mod))%mod;
        b/=2;
    }
    return ans;
}
/*ll comb(ll n, ll r) {
     if(r>n)return 0;
    return (((inv_fact[r]*inv_fact[n-r])%mod)*fact[n])%mod;
}
ll fact[5002];
ll comb(ll n, ll r) {
    if (r > n) return 0;
    ll ans = 0;
    ans = fact[n];
    ans *= mpow(fact[n - r], mod - 2);
    ans %= mod;
    ans *= mpow(fact[r], mod - 2);
    ans %= mod;
    return ans;
}
ll perm(ll n, ll r) {
    if (r > n) return 0;
    ll ans = 0;
    ans = fact[n];
    ans *= mpow(fact[n - r], mod - 2);
    ans %= mod;
    return ans;
}*/
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
vll a;
ll dp[2002][2002],n,p,q;
ll nex[2002][2];
ll rec(ll lev,ll rp,ll mid){
	if(lev>=n){
		return 0;
	}
	if(dp[lev][rp] != -1) return dp[lev][rp];
	ll ans=1e18;
	if(rp>0){
		ans = rec(nex[lev][0],rp-1,mid);
	}
	ans = min(ans,1 + rec(nex[lev][1],rp,mid));
	return dp[lev][rp] = ans;
}
int main(){
    fast;
    ll t=1;
   	//cin>>t;
    string s;
    while(t--){
    	cin>>n>>p>>q;
    	a.clear(),a.resize(n);
    	for(ll i=0;i<n;i++){
    		cin>>a[i];
    	}
    	sort(all(a));
    	if(n <= p+q){
    		cout<<1<<"\n";
    		continue;
    	}
    	ll lo = 1,hi = 1e9,ans=-1;	
    	while(lo<=hi){
    		ll mid = (lo+hi)/2;
    		for(ll i=0;i<=n;i++){
    			for(ll j=0;j<=n;j++){
    				dp[i][j]=-1;
    			}
    		}
    		for(ll i=0;i<n;i++){
    			nex[i][0] = lower_bound(a.begin(),a.end(),a[i] + mid) - a.begin();
    			nex[i][1] = lower_bound(a.begin(),a.end(),a[i] + 2*mid) - a.begin();	
    		}
    		if(rec(0,p,mid) <= q){
    			ans=mid;
    			hi=mid-1;
    		}
    		else{
    			lo=mid+1;
    		}
    	}
    	cout<<ans<<"\n";
    }
    return 0;
}

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