Submission #139202

#	Time	Username	Problem	Language	Result	Execution time	Memory
139202		SirCeness	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	111 ms	8696 KiB

railroad

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

ll mat[16][16];
int n;
ll dp[16][1<<16];

ll f(int node, int mask){
	if (mask == ((1<<n)-1)){
		return 0;
	}
	if (dp[node][mask] != -1) return dp[node][mask];
	ll ans = INF;
	for (int i = 0; i < n; i++){
		if ((mask & (1<<i)) == 0){
			ans = min(ans, f(i, mask|(1<<i)) + mat[node][i]);
		}
	}
	return dp[node][mask] = ans;
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
	n = (int) s.size();
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			mat[i][j] = max(0, t[i] - s[j]);
		}
	}
	
	for (int i = 0; i < n; i++) for (int j = 0; j < (1<<n); j++)
		dp[i][j] = -1;
	
	ll ans = INF;
	for (int i = 0; i < n; i++){
		ans = min(ans, f(i, (1<<i)));
	}
	return ans;
}

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