# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
299965 | T0p_ | Watching (JOI13_watching) | C++14 | 681 ms | 11776 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>
using namespace std;
int n, p, q;
long long arr[2020], dp[2020][2020];
int EndPoint(int s, long long w)
{
if(s > n) return n;
int l = s, r = n;
while(l != r)
{
int mid = (l+r+1)>>1;
(arr[s] + w - 1 >= arr[mid]) ? l = mid : r = mid-1;
}
return l;
}
bool Test(long long w)
{
for(int i=1 ; i<=p ; i++)
dp[i][0] = EndPoint(dp[i-1][0]+1, w);
for(int i=1 ; i<=q ; i++)
dp[0][i] = EndPoint(dp[0][i-1]+1, w+w);
for(int i=1 ; i<=p ; i++)
for(int j=1 ; j<=q ; j++)
dp[i][j] = max(EndPoint(dp[i-1][j]+1, w), EndPoint(dp[i][j-1]+1, w+w));
return dp[p][q] == n;
}
int main()
{
scanf(" %d %d %d",&n,&p,&q);
for(int i=1 ; i<=n ; i++)
scanf(" %lld",&arr[i]);
sort(arr+1, arr+n+1);
if(p+q >= n) printf("1\n");
else
{
long long l = 1, r = 1e9;
while(l != r)
{
long long mid = (l+r)>>1;
(Test(mid)) ? r = mid : l = mid + 1;
}
printf("%lld\n",l);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |