Submission #648338

#	Time	Username	Problem	Language	Result	Execution time	Memory
648338		jamezzz	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	2082 ms	23776 KiB

railroad

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

typedef long long ll;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pf printf
#define INF 1023456789
#define LINF 1023456789123456789

int n;
ll memo[20][65540];
vector<int> s,t;

ll dp(int i,int msk){
	if(memo[i][msk]!=-1)return memo[i][msk];
	if(msk==(1<<n)-1)return 0;
	ll res=LINF;
	for(int j=0;j<n;++j){
		if((msk&(1<<j))!=0)continue;
		res=min(res,max(t[i]-s[j],0)+dp(j,msk^(1<<j)));
	}
	return memo[i][msk]=res;
}

ll plan_roller_coaster(vector<int> _s,vector<int> _t){
	s=_s,t=_t;
    n=s.size();
    if(n<=16){
		memset(memo,-1,sizeof memo);
		ll ans=LINF;
		for(int i=0;i<n;++i){
			ans=min(ans,dp(i,1<<i));
		}
		return ans;
	}
	else{
		set<ii> ss,tt,sss;
		for(int i=0;i<n;++i){
			ss.insert({s[i],i});
			tt.insert({t[i],i});
		}
		while(ss.size()!=1){
			/*
			pf("ss: ");
			for(auto it:ss)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			pf("tt: ");
			for(auto it:tt)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			pf("sss: ");
			for(auto it:sss)pf("(%d %d) ",it.fi,it.se);
			pf("\n");
			*/
			while(!tt.empty()&&(*tt.begin()).fi<=(*ss.begin()).fi){
				int i=(*tt.begin()).se;
				sss.insert({s[i],i});
				tt.erase(tt.begin());
			}
			if(sss.empty()||(sss.size()==1&&(*sss.begin()).se==(*ss.begin()).se)){
				if((*--ss.end()).fi!=INF){
					int i=(*ss.begin()).se;
					ss.erase(ss.begin());
					sss.erase({s[i],i});
					s[i]=INF;
					tt.insert({t[i],i});
					ss.insert({INF,i});
				}
				else{
					return 1;
				}
			}
			else{
				//take the one with lowest s
				auto it=sss.begin();
				if((*sss.begin()).se==(*ss.begin()).se){
					it=next(it);
				}
				auto[_,i]=*ss.begin();
				auto[__,j]=*it;
				ss.erase(ss.begin());
				ss.erase({s[j],j});
				tt.erase({t[i],i});
				sss.erase({t[i],i});
				sss.erase(it);
				//new s[j]->t[i];
				t[j]=t[i];
				ss.insert({s[j],j});
				tt.insert({t[j],j});
			}
		}
		return 0;
	}
}

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