Submission #276955

#	Time	Username	Problem	Language	Result	Execution time	Memory
276955		eohomegrownapps	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	962 ms	22520 KiB

railroad

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

vector<vector<ll>> dp;

ll ans(ll state, int ind, int n, vector<int> &s, vector<int> &t){
	//state -- used indices
	//ind -- last used (so can take anything with s value >= t[i]
	/*for (int i = 0; i<n; i++){
		cout<<bool((1<<i)&state)<<' ';
	}*/
	//cout<<' '<<ind<<'\n'; 
	if (state==(1<<n)-1){
		return 0;
	}
	if (dp[state][ind]!=-1){return dp[state][ind];}
	ll minv = 1e18;
	for (int i = 0; i<n; i++){
		if ((1<<i)&state){continue;}
		//cost from ind to i
		ll cost = max(t[ind]-s[i],0);
		minv = min(minv,cost+ans(state+(1<<i),i,n,s,t));
	}
	return dp[state][ind]=minv;
}

ll subtask2(vector<int> &s, vector<int> &t){
	int n = s.size();
	dp.resize((1<<n),vector<ll>(n,-1));
	ll minv = 1e18;
	for (int i = 0; i<n; i++){
		minv=min(minv,ans((1<<i),i,n,s,t));
	}
	return minv;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    /*if (n<=16){
    	return subtask2(s,t);
    }*/
    multiset<pair<int,int>> lrset;
    multiset<pair<int,int>> rlset;
    for (int i = 0; i<n; i++){
    	lrset.insert({s[i],t[i]});
    	rlset.insert({t[i],s[i]});
    }
    ll tot = 0;
    while (lrset.size()>1){
    	/*cout<<'\n';
    	for (auto p : lrset){
    		cout<<p.first<<' '<<p.second<<'\n';
    	}*/
    	auto el = lrset.begin();
    	int firstl = el->first;
    	auto smallestrpair = rlset.lower_bound({firstl+1,-1});
    	if (smallestrpair!=rlset.begin()&&*prev(smallestrpair,1)==make_pair(el->second,el->first)){
    		smallestrpair = rlset.lower_bound({el->second,el->first-1});
    	}
    	int fpairr, fpairl;
    	if (smallestrpair==rlset.begin()){
    		el = next(el,1);
    		firstl = el->first;
    		fpairl = el->first;
    		fpairr = el->second;
    		lrset.erase(lrset.find({fpairl,fpairr}));
    		rlset.erase(rlset.find({fpairr,fpairl}));
    		smallestrpair = rlset.lower_bound({firstl+1,-1});
	    	/*if (smallestrpair==rlset.begin()){
    			return 1;
    		}*/
    	} else {
    		fpairl = el->first;
    		fpairr = el->second;
    		lrset.erase(lrset.find({fpairl,fpairr}));
    		rlset.erase(rlset.find({fpairr,fpairl}));
    	}
    	if (smallestrpair!=rlset.begin()){
    		smallestrpair = prev(smallestrpair,1);
    	}
    	//merge el with smallestrpair
    	int spairl = smallestrpair->second;
    	int spairr = smallestrpair->first;
    	//cout<<fpairl<<' '<<fpairr<<' '<<spairl<<' '<<spairr<<'\n';
    	lrset.erase(lrset.find({spairl,spairr}));
    	rlset.erase(rlset.find({spairr,spairl}));
    	lrset.insert({spairl,fpairr});
    	rlset.insert({fpairr,spairl});
    	tot+=max(0,spairr-fpairl);
    }
    return tot;
}

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