Submission #1031580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031580		pcc	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	43 ms	37368 KiB

railroad

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

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>

const ll inf = 1e18;
const int mxn = 18;
ll paths[mxn][mxn];
ll dp[mxn][1<<mxn];

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	int N = (int)s.size();
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			paths[i][j] = max(0,t[i]-s[j]);
		}
	}


	for(auto &i:dp)for(auto &j:i)j = inf;
	for(int i = 0;i<N;i++){
		dp[i][1<<i] = 0;
	}
	for(int i = 0;i<(1<<N);i++){
		for(int j = 0;j<N;j++){
			if(!(i&(1<<j)))continue;
			for(int k = 0;k<N;k++){
				if(i&(1<<k))continue;
				dp[k][i^(1<<k)] = min(dp[k][i^(1<<k)],dp[j][i]+paths[j][k]);
			}
		}
	}
	ll ans = inf;
	for(int i = 0;i<N;i++)ans = min(ans,dp[i][(1<<N)-1]);
	return ans;
}

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