oj.uz

Submission #54837

# Submission time Handle Problem Language Result Execution time Memory
54837 2018-07-05T08:05:15 Z ernestvw Rice Hub (IOI11_ricehub) C++11
49 / 100
 32 ms 17328 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 384 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 3 ms 536 KB Output is correct
5 Correct 2 ms 588 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 924 KB Output is correct
4 Correct 2 ms 924 KB Output is correct
5 Correct 2 ms 932 KB Output is correct
6 Correct 2 ms 976 KB Output is correct
7 Correct 2 ms 984 KB Output is correct
8 Correct 3 ms 992 KB Output is correct
9 Correct 2 ms 992 KB Output is correct
10 Incorrect 2 ms 996 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1000 KB Output is correct
2 Correct 3 ms 1060 KB Output is correct
3 Correct 3 ms 1064 KB Output is correct
4 Correct 3 ms 1088 KB Output is correct
5 Incorrect 2 ms 1112 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1756 KB Output is correct
2 Correct 7 ms 1892 KB Output is correct
3 Correct 23 ms 5228 KB Output is correct
4 Correct 28 ms 6312 KB Output is correct
5 Correct 12 ms 6312 KB Output is correct
6 Correct 11 ms 6312 KB Output is correct
7 Correct 26 ms 7688 KB Output is correct
8 Correct 25 ms 8456 KB Output is correct
9 Correct 12 ms 8456 KB Output is correct
10 Correct 11 ms 8456 KB Output is correct
11 Correct 22 ms 10112 KB Output is correct
12 Correct 22 ms 11128 KB Output is correct
13 Correct 12 ms 11128 KB Output is correct
14 Correct 10 ms 11128 KB Output is correct
15 Correct 32 ms 12072 KB Output is correct
16 Correct 32 ms 12876 KB Output is correct
17 Correct 25 ms 14176 KB Output is correct
18 Correct 25 ms 15120 KB Output is correct
19 Correct 26 ms 16320 KB Output is correct
20 Correct 25 ms 17328 KB Output is correct