Submission #853057

#	Time	Username	Problem	Language	Result	Execution time	Memory
853057		qin	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	39 ms	18768 KiB

railroad

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n");
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
int inf = 1e09; ll infll = 1e18;
ll plan_roller_coaster(vector<int> s, vector<int> e){
		int n = ssize(s);
		vector<vector<ll>> dp(n);
		for(int i = 0; i < n; ++i) dp[i].resize(1<<n, infll), dp[i][1<<i] = 0;
		for(int m = 1; m < 1<<n; ++m)
				for(int i = 0; i < n; ++i) if(m & (1<<i))
						for(int j = 0; j < n; ++j) if(~m & (1<<j)) dp[j][1<<j|m] = min(dp[j][1<<j|m], dp[i][m] + max(0, e[i]-s[j]));
		ll result = infll;
		for(int i = 0; i < n; ++i) result = min(result, dp[i][(1<<n)-1]);
		return result;
}
#ifdef LOCAL
int main(){
		int n; scanf("%d", &n);
		vector<int> s(n), e(n);
		for(int i = 0; i < n; ++i) scanf("%d", &s[i]);
		for(int i = 0; i < n; ++i) scanf("%d", &e[i]);
		ll result = plan_roller_coaster(s, e);
		printf("%lld\n", result);
		return 0;
}
#endif

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