Submission #1053694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053694		EntityPlantt	Rail (IOI14_rail)	C++17	30 / 100	35 ms	3412 KiB

rail

#include "rail.h"
// #include <iostream>

const int N = 5005;
int dp[N][N];
int dist(int i, int j) {
	if (i == j) return 0;
	if (i > j) {
		int t = i;
		i = j;
		j = t;
	}
	if (!dp[i][j]) {
		dp[i][j] = getDistance(i, j);
		// std::cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << std::endl;
	}
	return dp[i][j];
}
void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first;
	stype[0] = 1;
	int cr = 1;
	for (int i = 2; i < n; i++) if (dist(0, cr) > dist(0, i)) cr = i;
	location[cr] = dist(0, cr) + first;
	stype[cr] = 2;
	for (int i = 1; i < n; i++) {
		if (i == cr) continue;
		if (dist(0, i) > dist(cr, i)) {
			stype[i] = 1;
			location[i] = first - dist(cr, i) + dist(cr, 0);
		}
		else {
			stype[i] = 2;
			location[i] = first + dist(0, i);
		}
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44