Submission #405104

#	Time	Username	Problem	Language	Result	Execution time	Memory
405104		rainboy	Shortcut (IOI16_shortcut)	C11	71 / 100	2033 ms	1328 KiB

shortcut

#include "shortcut_c.h"

#define N	1000000
#define INF	0x3f3f3f3f3f3f3f3f

long long min(long long a, long long b) { return a < b ? a : b; }

long long find_shortcut(int n, int *ll, int *dd, int c) {
	static long long xx[N];
	int i, j, k, l, d1, d2;
	long long lower, upper;

	for (i = 1; i < n; i++)
		xx[i] = xx[i - 1] + ll[i - 1];
	d1 = d2 = 0;
	for (i = 0; i < n; i++)
		if (d1 < dd[i])
			d2 = d1, d1 = dd[i];
		else if (d2 < dd[i])
			d2 = dd[i];
	lower = d1 + d2 - 1, upper = xx[n - 1] + d1 + d2;
	while (upper - lower > 1) {
		long long d = (lower + upper) / 2, p, q, r, s;
		int can, j1, j2;

		p = q = r = s = INF;
		for (k = 0; k < n; k++)
			for (l = k + 1; l < n; l++)
				if (dd[k] + dd[l] + xx[l] - xx[k] > d) {
					/* dd[k] + dd[l] + |xx[k] - xx[i]| + c + |xx[l] - xx[j]| <= d
					 *
					 * max(xx[k] - xx[i], xx[i] - xx[k]) + max(xx[l] - xx[j], xx[j] - xx[l])
					 * <= d - (dd[k] + dd[l] + c)
					 *
					 * xx[k] - xx[i] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
					 * xx[k] - xx[i] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
					 * xx[i] - xx[k] + xx[l] - xx[j] <= d - (dd[k] + dd[l] + c)
					 * xx[i] - xx[k] + xx[j] - xx[l] <= d - (dd[k] + dd[l] + c)
					 *
					 * - xx[i] - xx[j] <= d - (dd[k] + dd[l] + c + xx[k] + xx[l])
					 * - xx[i] + xx[j] <= d - (dd[k] + dd[l] + c + xx[k] - xx[l])
					 * + xx[i] - xx[j] <= d - (dd[k] + dd[l] + c - xx[k] + xx[l])
					 * + xx[i] + xx[j] <= d - (dd[k] + dd[l] + c - xx[k] - xx[l]) */
					p = min(p, d - (+ xx[k] + xx[l] + dd[k] + dd[l] + c));
					q = min(q, d - (+ xx[k] - xx[l] + dd[k] + dd[l] + c));
					r = min(r, d - (- xx[k] + xx[l] + dd[k] + dd[l] + c));
					s = min(s, d - (- xx[k] - xx[l] + dd[k] + dd[l] + c));
				}
		can = 0;
		for (i = 0, j1 = -1, j2 = n - 1; i < n; i++) {
			while (j1 + 1 < n && - xx[i] + xx[j1 + 1] <= q)
				j1++;
			while (j2 >= 0 && + xx[i] + xx[j2] > s)
				j2--;
			j = min(j1, j2);
			if (i < j && - xx[i] - xx[j] <= p && + xx[i] - xx[j] <= r) {
				can = 1;
				break;
			}
		}
		if (can)
			upper = d;
		else
			lower = d;
	}
	return upper;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3