Submission #289330

#	Time	Username	Problem	Language	Result	Execution time	Memory
289330		Saboon	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	2080 ms	8576 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 16;
const ll inf = 1e18;

ll dp[(1<<maxn)+10][maxn], adj[maxn][maxn];

ll plan_roller_coaster(vector<int> s, vector<int> t){
	int n = (int)s.size();
	vector<pair<int,int>> tmp(n);
	for (int i = 0; i < n; i++)
		tmp[i] = {s[i],t[i]};
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < n; i++)
		s[i] = tmp[i].first, t[i] = tmp[i].second;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i != j)
				adj[i][j] = max(0,t[i]-s[j]);
	memset(dp, 63, sizeof dp);
	for (int mask = 1; mask < (1 << n); mask++){
		for (int v = 0; v < n; v++){
			if (!(mask & (1<<v)))
				continue;
			int sub = mask^(1<<v);
			if (sub == 0 and v == 0)
				dp[mask][v] = 0;
			else
				for (int u = 0; u < n; u++)
					if (sub & (1 << u))
						dp[mask][v] = min(dp[mask][v], dp[sub][u]+adj[u][v]);
		}
	}
	ll answer = inf;
	for (int i = 0; i < n; i++)
		answer = min(answer, dp[(1<<n)-1][i]);
	return answer;
}

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