| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 85556 |
2018-11-20T22:40:56 Z |
KCSC |
Watching (JOI13_watching) |
C++14 |
|
250 ms |
14872 KB |
#include <bits/stdc++.h>
using namespace std;
const int DIM = 2005;
int pos[DIM], pos1[DIM], pos2[DIM], dp[DIM][DIM];
int main(void) {
#ifdef HOME
freopen("watching.in", "r", stdin);
freopen("watching.out", "w", stdout);
#endif
int n, p, q; cin >> n >> p >> q;
for (int i = 1; i <= n; ++i) {
cin >> pos[i]; }
sort(pos + 1, pos + n + 1);
int le = 1, ri = 1000000000;
while (le <= ri) {
int md = (le + ri) / 2;
for (int i = 1; i <= n; ++i) {
pos1[i] = pos2[i] = 0;
for (int j = 1; j < i; ++j) {
if (pos[i] - md >= pos[j]) {
pos1[i] = j; }
if (pos[i] - md * 2 >= pos[j]) {
pos2[i] = j; } }
for (int j = 0; j <= i; ++j) {
dp[i][j] = dp[pos2[i]][j] + 1;
if (j > 0) {
dp[i][j] = min(dp[i][j], dp[pos1[i]][j - 1]); } } }
int ans = 1000000000;
for (int i = 0; i <= min(p, n); ++i) {
ans = min(ans, dp[n][i]); }
if (ans <= q) {
ri = md - 1; }
else {
le = md + 1; } }
cout << le;
return 0; }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
3 ms |
840 KB |
Output is correct |
| 5 |
Correct |
3 ms |
896 KB |
Output is correct |
| 6 |
Correct |
3 ms |
908 KB |
Output is correct |
| 7 |
Correct |
3 ms |
940 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1112 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1172 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1172 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1172 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1172 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
219 ms |
14520 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14520 KB |
Output is correct |
| 3 |
Correct |
199 ms |
14544 KB |
Output is correct |
| 4 |
Correct |
200 ms |
14544 KB |
Output is correct |
| 5 |
Correct |
202 ms |
14584 KB |
Output is correct |
| 6 |
Correct |
190 ms |
14584 KB |
Output is correct |
| 7 |
Correct |
232 ms |
14728 KB |
Output is correct |
| 8 |
Correct |
210 ms |
14728 KB |
Output is correct |
| 9 |
Correct |
250 ms |
14768 KB |
Output is correct |
| 10 |
Correct |
202 ms |
14788 KB |
Output is correct |
| 11 |
Correct |
203 ms |
14788 KB |
Output is correct |
| 12 |
Correct |
213 ms |
14828 KB |
Output is correct |
| 13 |
Correct |
212 ms |
14828 KB |
Output is correct |
| 14 |
Correct |
214 ms |
14872 KB |
Output is correct |
| 15 |
Correct |
223 ms |
14872 KB |
Output is correct |
