Submission #410004

#	Time	Username	Problem	Language	Result	Execution time	Memory
410004		LucaDantas	Rail (IOI14_rail)	C++17	30 / 100	97 ms	504 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5010;

bool mark[maxn];

int dp[maxn][maxn];

int dist(int a, int b) { return dp[a][b] ? dp[a][b] : dp[a][b] = getDistance(a, b); }

void findLocation(int N, int first, int location[], int stype[])
{
	int menor = 0, d = 0x3f3f3f3f;
	for(int i = 1; i < N; i++)
		if(dist(0, i) < d) menor = i, d = dist(0, i);
	location[0] = first;
	location[menor] = first + d;
	for(int i = 1; i < N; i++) {
		if(dist(0, i) == d + dist(menor, i)) location[i] = location[menor] - dist(menor, i);
		else location[i] = first + dist(0, i);
	}
	for(int i = 0; i < N; i++)
		if(location[i] <= first) stype[i] = 1;
		else stype[i] = 2;
}

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