#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 2e3 + 10;
int N, P, Q, Nr[MAX_N];
int L[2][MAX_N], Dy[MAX_N][MAX_N];
int main() {
cin >> N >> P >> Q;
REPO(i, N) scanf("%d", &Nr[i]);
sort(Nr+1, Nr+N+1);
P = min(N, P), Q = min(N, Q);
int ans = -1;
for(int l=1, r=1e9; l<=r; ) {
int m = (l+r) >> 1;
int w[2] = {m, 2*m};
for(int k=0; k<2; k++) {
int l = 1;
for(int i=1; i<=N; i++) {
while(Nr[i] - w[k] >= Nr[l]) l++;
L[k][i] = l;
}
}
Dy[0][0] = 0;
for(int i=1; i<=N; i++) {
for(int j=0; j<=P; j++) Dy[i][j] = INF;
for(int j=0; j<=P; j++) {
if(j) Dy[i][j] = min(Dy[i][j], Dy[L[0][i]-1][j-1]);
Dy[i][j] = min(Dy[i][j], Dy[L[1][i]-1][j] + 1);
}
}
bool isCan = false;
for(int j=0; j<=P; j++) if(Dy[N][j] <= Q) isCan = true;
if(isCan) ans = m, r = m-1;
else l = m+1;
}
printf("%d\n", ans);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REPO(i, N) scanf("%d", &Nr[i]);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 15 |
Correct |
0 ms |
17824 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
17824 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17824 KB |
Output is correct |
| 3 |
Correct |
309 ms |
17824 KB |
Output is correct |
| 4 |
Correct |
423 ms |
17824 KB |
Output is correct |
| 5 |
Correct |
23 ms |
17824 KB |
Output is correct |
| 6 |
Correct |
386 ms |
17824 KB |
Output is correct |
| 7 |
Correct |
6 ms |
17824 KB |
Output is correct |
| 8 |
Correct |
33 ms |
17824 KB |
Output is correct |
| 9 |
Correct |
206 ms |
17824 KB |
Output is correct |
| 10 |
Correct |
439 ms |
17824 KB |
Output is correct |
| 11 |
Correct |
26 ms |
17824 KB |
Output is correct |
| 12 |
Correct |
196 ms |
17824 KB |
Output is correct |
| 13 |
Correct |
9 ms |
17824 KB |
Output is correct |
| 14 |
Correct |
6 ms |
17824 KB |
Output is correct |
| 15 |
Correct |
6 ms |
17824 KB |
Output is correct |
