Submission #241690

#	Time	Username	Problem	Language	Result	Execution time	Memory
241690		godwind	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	78 ms	8704 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <functional>

using namespace std;

template<typename T> void uin(T &a, T b) {
	if (b < a) a = b;
}

const long long INF = 1e18 + 228;

long long dp[(1 << 17) + 17][16];

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = (int)s.size();
	if (n <= 16) {
		for (int i = 0; i < (1 << n); ++i) {
			for (int j = 0; j < n; ++j) {
				dp[i][j] = INF;
			}
		}
		for (int fir = 0; fir < n; ++fir) {
			dp[1 << fir][fir] = 0;
		}
		for (int mask = 0; mask < (1 << n); ++mask) {
			for (int last = 0; last < n; ++last) {
				if (dp[mask][last] != INF) {
					for (int new_last = 0; new_last < n; ++new_last) {
						if ((mask >> new_last) & 1) continue;
						long long cur = dp[mask][last] + max(0, t[last] - s[new_last]);
						uin(dp[mask | (1 << new_last)][new_last], cur);
					}
				}
			}
		}
		long long answer = INF;
		for (int last = 0; last < n; ++last) {
			uin(answer, dp[(1 << n) - 1][last]);
		}
		return answer;
	}
    return 0;
}

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