Submission #464947

#	Time	Username	Problem	Language	Result	Execution time	Memory
464947		ace_in_the_hole	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	57 ms	10560 KiB

railroad

#include "railroad.h"

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

typedef long long Int;
const int MOD = 2004010501; //MOD > 2e9

const Int INF = 1e18;
int num_elems;
Int s[20], t[20];
Int cost[20][20];
Int dp[1 << 16][16];
void minimize(Int& var, const Int& val) { if (val < var) var = val; }
/*
view each road as a graph node, then "railroads" are, in fact, just edges between nodes.
sort increasingly by s
*/

Int solve()
{
  	if (num_elems > 16) return 0;

	for (int i = 0; i < num_elems; i++) 
		for (int j = 0; j < num_elems; j++) cost[i][j] = max(0LL, t[i] - s[j]);
	for (int msk = 0; msk < (1 << num_elems); msk++)
		for (int pos = 0; pos < num_elems; pos++) dp[msk][pos] = INF;
	for (int i = 0; i < num_elems; i++) dp[1 << i][i] = 0;
	for (int msk = 0; msk < (1 << num_elems); msk++)
		for (int pos = 0; pos < num_elems; pos++) if (dp[msk][pos] < INF)
			for (int nxt = 0; nxt < num_elems; nxt++) if (((msk >> nxt) & 1) == 0)
				minimize(dp[msk | (1 << nxt)][nxt], dp[msk][pos] + cost[pos][nxt]);
	Int ans = INF;
	const int FULL = (1 << num_elems) - 1;
	for (int pos = 0; pos < num_elems; pos++)
		minimize(ans, dp[FULL][pos]);
	return ans;
}


long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    ::num_elems = (int) s.size();
	for (int i = 0; i < num_elems; i++) ::s[i] = s[i], ::t[i] = t[i];
    return solve();
}

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