Submission #354291

#	Time	Username	Problem	Language	Result	Execution time	Memory
354291		tengiz05	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	212 ms	171628 KiB

railroad

#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> s, t;
ll dp[1<<19][19];
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
	s = sk, t = tk;
	n = s.size();
	memset(dp, 0x3f3f3f3f, sizeof(dp));
	for(int i=0;i<n;i++)dp[0][i] = 0, dp[(1<<i)][i] = 0;
	for(int mask = 1; mask < (1<<n); mask++){
		for(int en = 0; en < n; en++){
			if(!(mask & (1<<en)))continue;
			for(int i=0;i<n;i++){
				if(!(mask & (1<<i)) || i == en)continue;
				dp[mask][en] = min(dp[mask][en], dp[mask^(1<<en)][i] + max(0, t[i] - s[en]));
			}
		}
	}
	ll ans = 1e18;
	for(int i=0;i<n;i++){
		ans = min(ans, dp[(1<<n)-1][i]);
	}
	return ans;
}

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