제출 #421607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421607		Kevin_Zhang_TW	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	52 ms	8496 KiB

railroad

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 16;
const ll inf = 1ll << 55;
#include "railroad.h"

ll dp[1<<MAX_N][MAX_N];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

	if (n > 16) return 0;

	for (int i = 0;i < 1<<n;++i) 
		fill(dp[i], dp[i] + n, inf);

	for (int i = 0;i < n;++i) {
		dp[1<<i][i] = 0;
	}
	auto cost = [&](int i, int j) {
		return max(0, t[i] - s[j]);
	};
	for (int s = 1;s < 1<<n;++s) {
		for (int j = 0;j < n;++j) if (s>>j&1) {
			for (int k = 0;k < n;++k) if (~s>>k&1) {
				chmin(dp[s | (1<<k)][k], dp[s][j] + cost(j, k));
			}
		}
	}
	ll res = inf;
	for (int i = 0;i < n;++i) chmin(res, dp[ (1<<n)-1 ][i] );
	return res;

}

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