oj.uz

Submission #54839

# Submission time Handle Problem Language Result Execution time Memory
54839 2018-07-05T08:06:23 Z ernestvw Rice Hub (IOI11_ricehub) C++11
100 / 100
 37 ms 4016 KB 
#include <bits/stdc++.h>
using namespace std;

#include "ricehub.h"

#define int long long

int prefix[100003], suffix[100003];
int r, l, pos[100003];
int b;

int costLeft(int x, int g, int d) {
	int dst = x - pos[d];
	dst *= (d - g + 1LL);
	dst += suffix[g] - suffix[d+1] - (l - pos[d]) * (d - g + 1LL);
	return dst;
}

int costRight(int x, int g, int d) {
	int dst = pos[g] - x;
	dst *= (d - g + 1LL);
	dst += prefix[d] - prefix[g-1] - pos[g] * (d - g + 1LL);
	return dst;
}

int cost(int g, int d) {
	int x = pos[(g + d) / 2];
	return costLeft(x, g, (g+d)/2) + costRight(x, (g+d)/2+1, d);
}

bool ok(int g, int d) {
	return cost(g, d) <= b;
}

int32_t besthub(int32_t R, int32_t L, int32_t *X, long long B) {
	for(int i = 1; i <= R; i++) pos[i] = X[i-1];
	r = R, l = L, b = B;
	prefix[0] = suffix[R+1] = 0;
	for(int i = 1; i <= R; i++)
		prefix[i] = prefix[i-1] + pos[i];
	for(int i = R; i >= 1; i--)
		suffix[i] = suffix[i+1] + l - pos[i];
	int ans = 1;
	int j = -1;
	for(int i = 1; i <= R; i++) {
		if(j < i) {
			j = i;
		}
		ans = max(ans, j-i+1);
		while(j+1 <= R and ok(i, j+1)) {
			ans = max(ans, (j+1-i+1));
			j++;
		}
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 3 ms 744 KB Output is correct
12 Correct 4 ms 764 KB Output is correct
13 Correct 2 ms 816 KB Output is correct
14 Correct 3 ms 816 KB Output is correct
15 Correct 2 ms 816 KB Output is correct
16 Correct 2 ms 816 KB Output is correct
17 Correct 2 ms 816 KB Output is correct
18 Correct 2 ms 840 KB Output is correct
19 Correct 2 ms 840 KB Output is correct
20 Correct 2 ms 840 KB Output is correct
21 Correct 2 ms 840 KB Output is correct
22 Correct 2 ms 840 KB Output is correct
23 Correct 2 ms 840 KB Output is correct
24 Correct 2 ms 840 KB Output is correct
25 Correct 2 ms 840 KB Output is correct
26 Correct 3 ms 840 KB Output is correct
27 Correct 2 ms 840 KB Output is correct
28 Correct 2 ms 840 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 840 KB Output is correct
2 Correct 3 ms 840 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 2 ms 840 KB Output is correct
5 Correct 2 ms 840 KB Output is correct
6 Correct 2 ms 840 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 2 ms 840 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 4 ms 876 KB Output is correct
13 Correct 2 ms 912 KB Output is correct
14 Correct 2 ms 924 KB Output is correct
15 Correct 2 ms 932 KB Output is correct
16 Correct 2 ms 936 KB Output is correct
17 Correct 2 ms 940 KB Output is correct
18 Correct 2 ms 952 KB Output is correct
19 Correct 3 ms 956 KB Output is correct
20 Correct 2 ms 964 KB Output is correct
21 Correct 3 ms 1100 KB Output is correct
22 Correct 4 ms 1124 KB Output is correct
23 Correct 3 ms 1148 KB Output is correct
24 Correct 3 ms 1180 KB Output is correct
25 Correct 4 ms 1212 KB Output is correct
26 Correct 3 ms 1252 KB Output is correct
27 Correct 2 ms 1332 KB Output is correct
28 Correct 4 ms 1460 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1756 KB Output is correct
2 Correct 9 ms 1760 KB Output is correct
3 Correct 19 ms 3932 KB Output is correct
4 Correct 21 ms 3932 KB Output is correct
5 Correct 9 ms 3932 KB Output is correct
6 Correct 16 ms 3932 KB Output is correct
7 Correct 21 ms 3956 KB Output is correct
8 Correct 37 ms 4016 KB Output is correct
9 Correct 14 ms 4016 KB Output is correct
10 Correct 9 ms 4016 KB Output is correct
11 Correct 21 ms 4016 KB Output is correct
12 Correct 21 ms 4016 KB Output is correct
13 Correct 11 ms 4016 KB Output is correct
14 Correct 10 ms 4016 KB Output is correct
15 Correct 21 ms 4016 KB Output is correct
16 Correct 23 ms 4016 KB Output is correct
17 Correct 20 ms 4016 KB Output is correct
18 Correct 27 ms 4016 KB Output is correct
19 Correct 20 ms 4016 KB Output is correct
20 Correct 21 ms 4016 KB Output is correct