Submission #310667

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

railroad

#include "railroad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second

const ll INF = 1e18;

ll dp[1<<16][16];

ll plan_roller_coaster(vi s, vi t) {
	// for(auto u: s){
	// 	cout << u << " ";
	// }
	// for(auto u: t){
	// 	cout << u << " ";
	// }
	// cout << "\n";
	int n = sz(s);
	for(int i = 0; i < (1<<n); i++){
		for(int j = 0; j < n; j++){
			dp[i][j] = INF;
		}
	}

	for(int i = 0; i < n; i++){
		dp[(1<<i)][i] = 0;
	}

	for(int i = 1; i < (1<<n); i++){
		for(int j = 0; j < n; j++){
			//cout << i << " " << j << " " << dp[i][j] << "\n";
			for(int k = 0; k < n; k++){
				if(((i>>k)&1) == 1) continue;
				dp[i+(1<<k)][k] = min(dp[i+(1<<k)][k], dp[i][j]+max(0, t[j]-s[k]));
			}
		}
	}

	ll ans = INF;
	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