//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define il pair<int,ll>
#define ii pair<int,int>
#define lii pair<pair<ll,int>,il>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define vv vector
#define endl '\n'
using namespace std;
const int MAXN = 2e3+5;
const int INF = 1e8;
int arr[MAXN];
int n,p,q;
bool check(int w){
int dp[q][n];
FOR(i,q)FOR(j,n)dp[i][j] = INF;
FOR(i,q+1){
FOR(j,n){
// using a p here
auto it = lower_bound(arr,arr+n,arr[j]-w+1);
int prevInd = it-arr;
prevInd--;
if(prevInd == -1){
dp[i][j] = 1;
}else{
dp[i][j] = dp[i][prevInd] + 1;
}
// using a q here
if(i > 0){
it = lower_bound(arr,arr+n,arr[j]-2*w+1);
prevInd = it-arr;
prevInd--;
if(prevInd == -1){
dp[i][j] = 0;
}else{
dp[i][j] = min(dp[i][j],dp[i-1][prevInd]);
}
}
//cout << i << " " << j << " " << dp[i][j] << endl;
}
}
return dp[q][n-1] <= p;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> p >> q;
p = min(n,p);
q = min(n,q);
FOR(i,n)cin >> arr[i];
sort(arr,arr+n);
int lo = 1;
int hi = 1e9;
//cout << check(4) << endl;
while(lo < hi){
int mid = (lo+hi)/2;
if(check(mid)){
hi = mid;
}else{
lo = mid+1;
}
}
cout << hi << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
