Submission #405039

#	Time	Username	Problem	Language	Result	Execution time	Memory
405039		rainboy	Roller Coaster Railroad (IOI16_railroad)	C11	34 / 100	59 ms	8476 KiB

railroad

#include "railroad_c.h"
#include <string.h>

#define N	16
#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 plan_roller_coaster(int n, int *aa, int *bb) {
	static long long dp[1 << N][N];
	int i, j, b;
	long long x;

	for (b = 1; b < 1 << n; b++)
		memset(dp[b], 0x3f, n * sizeof *dp[b]);
	for (i = 0; i < n; i++)
		dp[1 << i][i] = 0;
	for (b = 1; b < 1 << n; b++)
		for (i = 0; i < n; i++) {
			x = dp[b][i];
			if (x == INF)
				continue;
			for (j = 0; j < n; j++)
				if ((b & 1 << j) == 0)
					dp[b | 1 << j][j] = min(dp[b | 1 << j][j], x + max(bb[i] - aa[j], 0));
		}
	x = INF;
	for (i = 0; i < n; i++)
		x = min(x, dp[(1 << n) - 1][i]);
	return x;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36