#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<ll> v;
ll n,P,Q,a[N],dp[N][N],val;
unordered_map<ll,ll> mp;
ll Find(ll x){
if (mp.count(x)) return mp[x];
ll p = lower_bound(v.begin(),v.end(),x) - v.begin() + 1; mp[x] = p;
return p;
}
ll f(ll pos,ll p){
if (pos > n) return 0;
if (dp[pos][p] != -1) return dp[pos][p];
ll ans = inf,nxt1 = Find(a[pos] + val),nxt2 = Find(a[pos] + val*2);
if (p) ans = f(nxt1,p - 1);
ans = min(ans,1 + f(nxt2,p));
return dp[pos][p] = ans;
}
bool chk(ll m){
memset(dp,-1,sizeof(dp)); val = m;
return f(1,P) <= Q;
}
int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".in", "r")){
freopen(task".in", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>P>>Q;
for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
if (P + Q >= n) return cout<<1,0;
ll l,m,h; l = 0; h = inf;
while(l <= h){
m = (l + h)/2;
if (chk(m)) h = m - 1;
else l = m + 1;
}
cout<<l;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
44 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~
watching.cpp:44:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
44 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~~
watching.cpp:45:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^~~
watching.cpp:45:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
45 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^
watching.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
40 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
138 ms |
31852 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
142 ms |
31852 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
147 ms |
31852 KB |
Output is correct |
8 |
Correct |
142 ms |
31980 KB |
Output is correct |
9 |
Correct |
145 ms |
31980 KB |
Output is correct |
10 |
Correct |
143 ms |
31980 KB |
Output is correct |
11 |
Correct |
147 ms |
31980 KB |
Output is correct |
12 |
Correct |
149 ms |
31980 KB |
Output is correct |
13 |
Correct |
152 ms |
32108 KB |
Output is correct |
14 |
Correct |
138 ms |
31852 KB |
Output is correct |
15 |
Correct |
139 ms |
31932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
147 ms |
31832 KB |
Output is correct |
2 |
Correct |
2 ms |
364 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
364 KB |
Output is correct |
7 |
Correct |
146 ms |
32236 KB |
Output is correct |
8 |
Correct |
417 ms |
33776 KB |
Output is correct |
9 |
Execution timed out |
1072 ms |
33824 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |