#include <bits/stdc++.h>
#define ll long long
#define MAXN 2010
using namespace std;
ll a[MAXN],n,p,q;
pair<ll,ll> dp[MAXN][MAXN];
ll Last(ll pos)
{
ll l=1,r=n,mid,ans;
while (l<=r)
{
mid=(l+r)/2;
if (a[mid]<=pos)
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return ans;
}
bool Check(ll w)
{
for (ll i=0;i<=n+1;i++)
{
for (ll j=0;j<=n+1;j++)
dp[i][j]={0,LLONG_MAX};
}
dp[1][0]={1,0};
for (ll i=1;i<=n;i++)
{
for (ll j=0;j<=p;j++)
{
if (!dp[i][j].first)
continue;
if (j<p)
{
ll pos=Last(a[i]+w-1);
dp[pos+1][j+1].first=1;
dp[pos+1][j+1].second=min(dp[pos+1][j+1].second,dp[i][j].second);
}
if (dp[i][j].second<q)
{
ll pos=Last(a[i]+2*w-1);
dp[pos+1][j].first=1;
dp[pos+1][j].second=min(dp[pos+1][j].second,dp[i][j].second+1);
}
}
}
for (ll i=0;i<=p;i++)
{
if (dp[n+1][i].first && dp[n+1][i].second<=q)
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> p >> q;
for (ll i=1;i<=n;i++)
cin >> a[i];
sort(a+1,a+1+n);
ll l=1,r=1e9,mid,ans;
while (l<=r)
{
mid=(l+r)/2;
if (Check(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
cout << ans;
return 0;
}
Compilation message
watching.cpp: In function 'long long int Last(long long int)':
watching.cpp:21:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return ans;
| ^~~
watching.cpp: In function 'bool Check(long long int)':
watching.cpp:46:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
46 | dp[pos+1][j].first=1;
| ~~~^~
watching.cpp:40:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
40 | dp[pos+1][j+1].first=1;
| ~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
313 ms |
1172 KB |
Output is correct |
5 |
Correct |
1 ms |
852 KB |
Output is correct |
6 |
Correct |
343 ms |
1176 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
1 ms |
852 KB |
Output is correct |
10 |
Correct |
1 ms |
852 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
1 ms |
852 KB |
Output is correct |
14 |
Correct |
1 ms |
852 KB |
Output is correct |
15 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
63316 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
782 ms |
63316 KB |
Output is correct |
4 |
Runtime error |
99 ms |
128228 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |