#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 rec(ll lev,ll rp,ll mid){
if(lev>=n){
return 0;
}
if(dp[lev][rp] != -1) return dp[lev][rp];
ll ans=1e18,nlev;
if(rp>0){
nlev = lower_bound(a.begin(),a.end(),a[lev] + mid) - a.begin();
ans = rec(nlev,rp-1,mid);
}
nlev = lower_bound(a.begin(),a.end(),a[lev] + (2*mid)) - a.begin();
ans = min(ans,1 + rec(nlev,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;
mem(dp,-1);
if(rec(0,p,mid) <= q){
ans=mid;
hi=mid-1;
}
else{
lo=mid+1;
}
}
cout<<ans<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
31668 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
105 ms |
31672 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
320 KB |
Output is correct |
| 7 |
Correct |
104 ms |
31668 KB |
Output is correct |
| 8 |
Correct |
100 ms |
31672 KB |
Output is correct |
| 9 |
Correct |
110 ms |
31664 KB |
Output is correct |
| 10 |
Correct |
104 ms |
31676 KB |
Output is correct |
| 11 |
Correct |
114 ms |
31668 KB |
Output is correct |
| 12 |
Correct |
103 ms |
31668 KB |
Output is correct |
| 13 |
Correct |
103 ms |
31564 KB |
Output is correct |
| 14 |
Correct |
97 ms |
31700 KB |
Output is correct |
| 15 |
Correct |
105 ms |
31564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
31704 KB |
Output is correct |
| 2 |
Correct |
0 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
105 ms |
31700 KB |
Output is correct |
| 8 |
Correct |
327 ms |
31712 KB |
Output is correct |
| 9 |
Correct |
764 ms |
31780 KB |
Output is correct |
| 10 |
Execution timed out |
1076 ms |
31864 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
