Submission #64967

#	Time	Username	Problem	Language	Result	Execution time	Memory
64967		FedericoS	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	505 ms	51800 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <assert.h>
#include <queue>
#include <utility>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int N;
ll ans=1e18;
ll S[1000006],T[1000006];
ll DP[1000006][20];
priority_queue<pll> PQS,PQT;
bool V[1000006];

ll F(int b, int i){

    assert(b&(1<<i));

	if(DP[b][i]!=-1)
		return DP[b][i];

	b=b^(1<<i);

	if(!b)
		return 0;

	ll res=1e18;
	for(int j=0;j<N;j++)
		if(b&(1<<j) and j!=i)
			res=min(res,F(b,j)+max(0LL,T[j]-S[i]));

	DP[b|(1<<i)][i]=res;
	return res;

}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {

    N=s.size();
	for(int i=0;i<N;i++)
        S[i]=s[i];
	for(int i=0;i<N;i++)
		T[i]=t[i];

    if(N>16){

        for(int i=0;i<N;i++){
            PQS.push({S[i],i});
            PQT.push({T[i],i});
        }

        S[N]=1e18;
        T[N]=-1;
        PQS.push({S[N],N});
        PQT.push({T[N],N});

        int cont=N+1,x,y;
        while(!PQS.empty() and !PQT.empty()){

            while(V[PQT.top().second] and !PQT.empty())
                PQT.pop();
            while(V[PQS.top().second] and !PQS.empty() and PQS.top().second!=PQT.top().second)
                PQS.pop();

            if(PQS.empty() or PQT.empty())
                return 0;

            x=PQT.top().second;
            y=PQS.top().second;

            if(T[x]<=S[y]){
                V[x]=true;
                V[y]=true;
                S[cont]=S[x];
                T[cont]=T[y];
                PQS.push({S[cont],cont});
                PQT.push({T[cont],cont});
                cont++;
            }
            else
                return 1;
        }
        return 0;
    }

	int b=(1<<N)-1;

	for(int i=0;i<N;i++)
		for(int j=0;j<=b;j++)
			DP[j][i]=-1;

	for(int i=0;i<N;i++)
		ans=min(ans,F(b,i));

	return ans;

}
/*
4
1 3
3 7
10 10
20 2
*/

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