Submission #405046

#	Time	Username	Problem	Language	Result	Execution time	Memory
405046		rainboy	Shortcut (IOI16_shortcut)	C11	23 / 100	2047 ms	288 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 max(long long a, long long b) { return a > b ? a : b; }
long long abs_(long long a) { return a > 0 ? a : -a; }

long long find_shortcut(int n, int *ll, int *dd, int c) {
	static long long xx[N];
	int i, j, k, l;
	long long d_, d;

	for (i = 1; i < n; i++)
		xx[i] = xx[i - 1] + ll[i - 1];
	d_ = INF;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++) {
			d = 0;
			for (k = 0; k < n; k++)
				for (l = k + 1; l < n; l++)
					d = max(d, dd[k] + dd[l] + min(abs_(xx[k] - xx[l]), abs_(xx[k] - xx[i]) + c + abs_(xx[j] - xx[l])));
			d_ = min(d_, d);
		}
	return d_;
}

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