Submission #134745

#	Time	Username	Problem	Language	Result	Execution time	Memory
134745		ckodser	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	211 ms	12984 KiB

railroad

#include "railroad.h"

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define F first
#define S second
#define ld long double

using namespace :: std;

const ll maxn=16;
const ll inf=1e17+900;

ll ger[maxn][maxn];
ll dp[1<<maxn][maxn];

ll solve17(vector<int> s,vector<int> t){
    ll n=s.size();
    for(ll i=0;i<n;i++){
	for(ll j=0;j<n;j++){
	    ger[i][j]=max(0,t[i]-s[j]);
	}
    }
    for(ll i=1;i<(1<<n);i++){
	for(ll j=0;j<n;j++){
	    if(i!=(1<<j)){
		if((i>>j)&1){
		    dp[i][j]=inf;
		    for(ll k=0;k<n;k++){
			if(((i>>k)&1) && k!=j){
			    dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+ger[j][k]);
			}
		    }	
		}
	    }
	}
    }
    ll ans=inf;
    for(ll i=0;i<n;i++){
	ans=min(ans,dp[(1<<n)-1][i]);
    }
    return ans;
}



long long plan_roller_coaster(vector<int> s,vector<int> t) {
    if(s.size()<=16){
	return solve17(s,t);
    }
    t.pb(1);
    s.pb(inf);

    int n = (int) s.size();
    vector<pii> vec;
    for(ll i=0;i<n;i++){
	ll v=s[i];
	vec.pb(mp(v,(i+1)));
    }
    for(ll i=0;i<n;i++){
	ll v=t[i];
	vec.pb(mp(v,-(i+1)));
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    vector<ll> invecs,invect;
    invecs.resize(n);invect.resize(n);

    for(ll i=0;i<vec.size();i++){
	pii e=vec[i];
	ll v=e.F;
	ll w=e.S;
	ll x=abs(w)-1;
	if(w<0){
	    invect[x]=i;
	}else{
	    invecs[x]=i;
	}
    }

    ll sum=0;
    ll mnn=inf;
    for(ll i=0;i<vec.size();i++){
	pii e=vec[i];
	ll v=e.F;
	ll w=e.S;
	ll x=abs(w)-1;
	if(w<0){
	    mnn=max(mnn,invecs[x]);
	    sum--;
	}else{
	    sum++;
	}
	if(sum<0)return 1;
	if(sum==0){
	    if(mnn<=i && i!=vec.size()-1){
		return 1;
	    }
	}
    }
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:55:13: warning: overflow in implicit constant conversion [-Woverflow]
     s.pb(inf);
             ^
railroad.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<vec.size();i++){
                ~^~~~~~~~~~~
railroad.cpp:74:5: warning: unused variable 'v' [-Wunused-variable]
  ll v=e.F;
     ^
railroad.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<vec.size();i++){
                ~^~~~~~~~~~~
railroad.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(mnn<=i && i!=vec.size()-1){
                   ~^~~~~~~~~~~~~~
railroad.cpp:88:5: warning: unused variable 'v' [-Wunused-variable]
  ll v=e.F;
     ^

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