Submission #64866

#	Time	Username	Problem	Language	Result	Execution time	Memory
64866		yogahmad	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	647 ms	24264 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>
using namespace std;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
int n;
long long dep[18][(1<<16)+10];
vector<int>S,T;

long long dp(int now,int mask){
	if(__builtin_popcount(mask)==n)return 0;
	long long&ret=dep[now][mask];
	if(ret!=-1)return ret;
	ret=1e18;
	for(int i=0;i<n;i++){
		if(!(mask&(1<<i))){
			long long cost=0;
			if(T[now]>=S[i])cost=T[now]-S[i];
			int nex=mask|(1<<i);
			ret=min(ret,dp(i,nex)+cost);
		}
	}
	return ret;
}

map<int,int>cnt;

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    n=s.size();
    S=s;
    T=t;
    if(n<=16){
    	T.pb(1);
    	reset(dep,-1);
    	return dp(n,0);
	}
	cnt[1]++;
	for(int i:s){
		cnt[i]--;
	}
	for(int i:t){
		cnt[i]++;
	}
	int ada=0;
	for(auto i:cnt){
		if(i.s!=0){
			if(!ada)ada=1;
			else{
				return 1;
			}
		}
	}
    return 0;
}

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