Submission #239556

#	Time	Username	Problem	Language	Result	Execution time	Memory
239556		Fasho	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	105 ms	32224 KiB

railroad

#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
#include "railroad.h"
using namespace std;

ll n,m,ar[N],sum,t,pw[N];

ll dp[20][70000];

ii p[N];

ll f(ll ind,ll mask)
{
	if(mask==pw[n]-1)
		return 0;
	if(dp[ind][mask]!=-1)
		return dp[ind][mask];
	ll top=1e18;
	fo(i,0,n-1)
	{
		if((mask & pw[i]))
			continue; 
		ll x=(mask | pw[i]);
		top=min(top,f(i,x) + max(0,p[ind].se-p[i].fi));
	}
	// cout<<"[d]"<<sp<<ind<<sp<<mask<<sp<<top<<endl;
	return dp[ind][mask]=top;
}


long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    n = (int) s.size();
    memset(dp,-1,sizeof(dp));
    pw[0]=1;
    fo(i,1,20)
    pw[i]=pw[i-1]*2;
    fo(i,0,t.size()-1)
    if(t[i]==0)
    	return 0;
    fo(i,0,s.size()-1)
    if(s[i]==0)
    	return 0;
    fo(i,0,n-1)
    	p[i]={s[i],t[i]};
    ll x=1e18;
    fo(i,0,n-1)
    x=min(x,f(i,pw[i]));
    return x;
    // return 1;
}

// vector<int> a,b;
// int main()
// {
// 	fast;
// 	cin>>n;
// 	fo(i,1,n)
// 	{
// 		int x,y;
// 		cin>>x>>y;
// 		a.pb(x);
// 		b.pb(y);
// 	}
// 	cout<<plan_roller_coaster(a,b);

// }

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fo(i,x,y) for(ll i=x;i<=y;i++)
railroad.cpp:54:8:
     fo(i,0,t.size()-1)
        ~~~~~~~~~~~~~~          
railroad.cpp:54:5: note: in expansion of macro 'fo'
     fo(i,0,t.size()-1)
     ^~
railroad.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fo(i,x,y) for(ll i=x;i<=y;i++)
railroad.cpp:57:8:
     fo(i,0,s.size()-1)
        ~~~~~~~~~~~~~~          
railroad.cpp:57:5: note: in expansion of macro 'fo'
     fo(i,0,s.size()-1)
     ^~

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