/***Farhan132***/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast,fast-math")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
const ll mod = (ll) 998244353;
//const ll mod = (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = (ll)1e18;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
bool USACO = 0;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 2005;
ll dp[N][N], a[N];
void solve(){
ll n , p , q; cin >> n >> p >> q;
q = min(n, q);
a[0] = 0;
for(ll i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
mem(dp, 0);
ll ans = 1e9;
ll lo = 1, hg = 1e9;
while(lo <= hg){
ll mid = (lo + hg)/2;
for(ll i = 1; i <= n; i++){
ll x = -1, y = -1;
for(ll j = i - 1; j >= 0; j--){
if(x == -1 && a[j] < (a[i] - mid + 1)) x = j;
if(y == -1 && a[j] < (a[i] - 2*mid + 1)) y = j;
}
if(x == -1) x = 0;
if(y == -1) y = 0;
for(ll j = 0; j <= i; j++){
dp[i][j] = dp[x][j] + 1;
if(j) dp[i][j] = min(dp[i][j], dp[y][j - 1]);
}
}
if(dp[n][q] <= p) ans = mid, hg = mid - 1;
else lo = mid + 1;
}
cout << ans << '\n';
return;
}
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
freopen("out", "w", stdout);
auto start_time = clock();
#else
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#endif
//pre(N);
ll T = 1, CT = 0; //cin >> T;
while(T--){
// cout << "Case #" << ++CT <<": " ;
solve();
}
#ifdef LOCAL
auto end_time = clock();
cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n";
#endif
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:121:15: warning: unused variable 'CT' [-Wunused-variable]
121 | ll T = 1, CT = 0; //cin >> T;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 2 |
Correct |
13 ms |
31796 KB |
Output is correct |
| 3 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
15 ms |
31680 KB |
Output is correct |
| 5 |
Correct |
14 ms |
31824 KB |
Output is correct |
| 6 |
Correct |
16 ms |
31732 KB |
Output is correct |
| 7 |
Correct |
14 ms |
31696 KB |
Output is correct |
| 8 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 9 |
Correct |
14 ms |
31692 KB |
Output is correct |
| 10 |
Correct |
14 ms |
31696 KB |
Output is correct |
| 11 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 12 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 13 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 14 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 15 |
Correct |
13 ms |
31700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
200 ms |
31824 KB |
Output is correct |
| 2 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 3 |
Correct |
174 ms |
31808 KB |
Output is correct |
| 4 |
Correct |
169 ms |
31828 KB |
Output is correct |
| 5 |
Correct |
209 ms |
31808 KB |
Output is correct |
| 6 |
Correct |
186 ms |
31812 KB |
Output is correct |
| 7 |
Correct |
172 ms |
31828 KB |
Output is correct |
| 8 |
Correct |
178 ms |
31828 KB |
Output is correct |
| 9 |
Correct |
173 ms |
31828 KB |
Output is correct |
| 10 |
Correct |
174 ms |
31808 KB |
Output is correct |
| 11 |
Correct |
180 ms |
31816 KB |
Output is correct |
| 12 |
Correct |
177 ms |
31828 KB |
Output is correct |
| 13 |
Correct |
177 ms |
31816 KB |
Output is correct |
| 14 |
Correct |
181 ms |
31700 KB |
Output is correct |
| 15 |
Correct |
170 ms |
31808 KB |
Output is correct |
