Submission #765816

#	Time	Username	Problem	Language	Result	Execution time	Memory
765816		SanguineChameleon	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	36 ms	10680 KiB

railroad

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

const long long inf = 1e18L + 20;
long long dp[1 << 16][16];

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = s.size();
	for (int mask = 0; mask < (1 << n); mask++) {
		for (int i = 0; i < n; i++) {
			dp[mask][i] = inf;
		}
	}
	for (int i = 0; i < n; i++) {
		dp[1 << i][i] = 0;
	}
	for (int mask = 1; mask < (1 << n); mask++) {
		for (int i = 0; i < n; i++) {
			if (dp[mask][i] == inf) {
				continue;
			}
			for (int j = 0; j < n; j++) {
				if (((mask >> j) & 1) == 0) {
					dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + max(t[i] - s[j], 0));
				}
			}
		}
	}
	long long res = inf;
	for (int i = 0; i < n; i++) {
		res = min(res, dp[(1 << n) - 1][i]);
	}
	return res;
}

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