// IOI 2011
// Day 1 Problem 3, Rice Hub
#include <iostream>
#include <ricehub.h>
using namespace std;
/*
* Idea: sliding window on range -
* if less dist take max?
* median is the location of hub
*/
typedef long long ll;
ll psum[100005];
ll cst(int R, int l, int r)
{
if (l == r) return 0;
int mid = (l + r) / 2;
if ((r - l) % 2) return psum[r] - psum[mid] - (psum[mid] - (l ? psum[l - 1] : 0));
else return psum[r] - psum[mid] - (psum[mid - 1] - (l ? psum[l - 1] : 0));
}
// R: number of rice fields
// L: longest dist
// X: all the field's locations
// B: max number spent
// return best r - l + 1
int besthub(int R, int L, int X[], ll B)
{
psum[0] = X[0];
for (int i = 1; i < R; i++)
psum[i] = psum[i - 1] + X[i];
int l = 0, r = 0, ans = 1;
while (r < R)
{
if (cst(R, l, r) <= B) ans = max(ans, r - l + 1);
while (r + 1 < R && cst(R, l, r + 1) <= B)
{
++r;
ans = max(ans, r - l + 1);
}
while (cst(R, l, r) > B)
++l;
++r;
}
return ans;
}
//int main()
//{
// int arr[] = { 1, 4, 10, 11, 14 };
// cout << besthub(5, 20, arr, 18);
// return 0;
//}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
308 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
304 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
296 KB |
Output is correct |
| 15 |
Correct |
0 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
308 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
| 23 |
Correct |
1 ms |
224 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
212 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
0 ms |
212 KB |
Output is correct |
| 28 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
304 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
312 KB |
Output is correct |
| 21 |
Correct |
1 ms |
320 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
2 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
360 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
324 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Correct |
3 ms |
568 KB |
Output is correct |
| 3 |
Correct |
11 ms |
2428 KB |
Output is correct |
| 4 |
Correct |
11 ms |
2480 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1220 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1236 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2148 KB |
Output is correct |
| 8 |
Correct |
10 ms |
2220 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1076 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1092 KB |
Output is correct |
| 11 |
Correct |
11 ms |
2440 KB |
Output is correct |
| 12 |
Correct |
11 ms |
2516 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1236 KB |
Output is correct |
| 14 |
Correct |
8 ms |
1216 KB |
Output is correct |
| 15 |
Correct |
9 ms |
1876 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1888 KB |
Output is correct |
| 17 |
Correct |
10 ms |
2236 KB |
Output is correct |
| 18 |
Correct |
10 ms |
2212 KB |
Output is correct |
| 19 |
Correct |
11 ms |
2400 KB |
Output is correct |
| 20 |
Correct |
10 ms |
2388 KB |
Output is correct |
