| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 498971 | Karabasan | Watching (JOI13_watching) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")
int n,m,ar[2005],p,q;
int dp[2005][2005];
bool check(int w)
{
int lp=0,lq=0;
memset(dp,0,sizeof(dp));
for(ll i=1;i<=n;i++)
{
while(ar[lp+1]<=ar[i]-w)
lp++;
while(ar[lq+1]<=ar[i]-2*w)
lq++;
for(int j=0;j<=min(i,p);j++)
{
if(j==0)
{
dp[i][j]=dp[lq][0]+1;
continue;
}
int t1=dp[lp][j-1];
int t2=dp[lq][j]+1;
dp[i][j]=min(t1,t2);
}
}
if(dp[n][min(n,p)]>q)
return false;
return true;
}
int main()
{
fast1;
cin>>n>>p>>q;
for(int i=1;i<=n;i++)
cin>>ar[i];
sort(ar+1,ar+n+1);
int bas=0;
int son=1e14;
while(bas<son)
{
int orta=(bas+son)/2;
if(check(orta))
son=orta;
else bas=orta+1;
}
cout<<bas;
}