Submission #405068

#	Time	Username	Problem	Language	Result	Execution time	Memory
405068		rainboy	Shortcut (IOI16_shortcut)	C11	71 / 100	2057 ms	1324 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;
	long long lower, upper;

	for (i = 1; i < n; i++)
		xx[i] = xx[i - 1] + ll[i - 1];
	lower = -1, upper = xx[n - 1] + 2000000000;
	while (upper - lower > 1) {
		long long d = (lower + upper) / 2, w, x, y, z;
		int can;

		w = x = y = z = 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]) */
					w = min(w, d - (+ xx[k] + xx[l] + dd[k] + dd[l] + c));
					x = min(x, d - (+ xx[k] - xx[l] + dd[k] + dd[l] + c));
					y = min(y, d - (- xx[k] + xx[l] + dd[k] + dd[l] + c));
					z = min(z, d - (- xx[k] - xx[l] + dd[k] + dd[l] + c));
				}
		can = 0;
		for (i = 0; i < n; i++)
			for (j = i + 1; j < n; j++)
				if (- xx[i] - xx[j] <= w && - xx[i] + xx[j] <= x && + xx[i] - xx[j] <= y && + xx[i] + xx[j] <= z) {
					can = 1;
					goto out;
				}
out:
		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