# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
156463 | wilwxk | Watching (JOI13_watching) | C++14 | 181 ms | 8692 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;
const int MAXN=2e3+3;
int v[MAXN], chega[MAXN][2];
int dp[MAXN][MAXN];
int n, x, y;
bool testa(int k) {
int p=1, p2=1;
for(int i=1; i<=n; i++) {
while(p<=n&&v[p]-v[i]<=k-1) p++;
while(p2<=n&&v[p2]-v[i]<=2*k-1) p2++;
chega[i][0]=p;
chega[i][1]=p2;
}
chega[0][0]=chega[0][1]=1;
chega[n+1][0]=chega[n+1][1]=n+1;
for(int i=0; i<=x; i++) {
for(int j=0; j<=y; j++) {
dp[i][j]=1;
if(i!=0) dp[i][j]=max(dp[i][j], chega[dp[i-1][j]][0]);
if(j!=0) dp[i][j]=max(dp[i][j], chega[dp[i][j-1]][1]);
// printf("%d %d >> %d\n", i, j, dp[i][j]);
}
}
return dp[x][y]>n;
}
int main() {
scanf("%d %d %d", &n, &x, &y);
if(x+y>=n) {
printf("1\n");
return 0;
}
for(int i=1; i<=n; i++) scanf("%d", &v[i]);
sort(v+1, v+1+n);
for(int i=1; i<=n; i++) {
}
// testa(4);
int respf=0;
for(int i=1e9; i>0; i/=2) while(!testa(respf+i)) respf+=i;
printf("%d\n", respf+1);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |