# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
366311 |
2021-02-13T20:54:11 Z |
idk321 |
Watching (JOI13_watching) |
C++11 |
|
1000 ms |
16256 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int dp[N][N];
int n,p, q;
int a[N];
bool poss(ll w)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++) dp[i][j] = 0;
}
for (int i = p; i >= 0; i--)
{
for (int j = q; j >= 0; j--)
{
if (dp[i][j] == n)
{
dp[0][0] = n;
} else
{
if (i != 0)
{
int first = a[dp[i][j]];
auto it = upper_bound(a, a + n, first + w - 1);
it--;
dp[i - 1][j] = max<int>(it - a + 1, dp[i - 1][j]);
}
if (j != 0)
{
int first = a[dp[i][j]];
auto it = upper_bound(a, a + n, first + 2 * w - 1);
it--;
dp[i][j - 1] = max<int>(it - a + 1, dp[i][j -1]);
}
}
}
}
return dp[0][0] == n;
}
int bs()
{
int a = 2;
int b = 1000000000;
int res = -1;
while (a <= b)
{
int mid = (a + b) / 2;
if (poss(mid))
{
res = mid;
b = mid - 1;
} else
{
a = mid + 1;
}
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> p >> q;
for (int i = 0; i < n; i++) cin >> a[i];
if (p + q >= n)
{
cout << 1 << "\n";
return 0;
}
sort(a, a + n);
cout << bs() << "\n";
}
/*
3 1 1
2
11
17
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
16132 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
86 ms |
16256 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
89 ms |
16108 KB |
Output is correct |
8 |
Correct |
88 ms |
16108 KB |
Output is correct |
9 |
Correct |
86 ms |
16108 KB |
Output is correct |
10 |
Correct |
87 ms |
16108 KB |
Output is correct |
11 |
Correct |
87 ms |
16108 KB |
Output is correct |
12 |
Correct |
89 ms |
16108 KB |
Output is correct |
13 |
Correct |
88 ms |
16236 KB |
Output is correct |
14 |
Correct |
87 ms |
16236 KB |
Output is correct |
15 |
Correct |
87 ms |
16108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
16108 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
412 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
88 ms |
16236 KB |
Output is correct |
8 |
Correct |
279 ms |
16108 KB |
Output is correct |
9 |
Correct |
239 ms |
16236 KB |
Output is correct |
10 |
Correct |
335 ms |
16156 KB |
Output is correct |
11 |
Correct |
471 ms |
16236 KB |
Output is correct |
12 |
Execution timed out |
1086 ms |
16108 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |