Submission #399283

#	Time	Username	Problem	Language	Result	Execution time	Memory
399283		peuch	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	304 ms	14424 KiB

railroad

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

const long long INF = 1e18;

int n;
vector<int> S, T;

long long ans = 1e18;

long long dp[20][1<<18];
bool marc[20][1<<18];

long long getDP(int cur, int mask);

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	S = s;
	T = t;
    n = s.size();
	multiset<pair<int, int> > aux;
    
	for(int i = 0; i < n; i++){
		if(n <= 16) ans = min(ans, getDP(i, (1 << n) - 1));
		aux.insert(make_pair(T[i], -S[i]));
	}
	
	if(n <= 16) return ans;
	
	int upb = 1e9;
	for(int i = 0; i < n; i++){
		multiset<pair<int, int> > :: iterator it = aux.upper_bound(make_pair(upb, 1e9));
		if(it == aux.begin()) return 1;
		it--;
		upb = -it->second;
		aux.erase(it);
	}
	return 0;
}

long long getDP(int cur, int mask){
	if(marc[cur][mask]) return dp[cur][mask];
	marc[cur][mask] = 1;
	dp[cur][mask] = INF;
	if(!((1 << cur) & mask)) return dp[cur][mask] = INF;
	if(!((1 << cur) ^ mask)) return dp[cur][mask] = 0;
	for(int i = 0; i < n; i++)
		dp[cur][mask] = min(dp[cur][mask], getDP(i, mask ^ (1 << cur)) + max(0, T[i] - S[cur]));
	return dp[cur][mask];
}

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