Submission #162527

#	Time	Username	Problem	Language	Result	Execution time	Memory
162527		MohamedAhmed04	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	125 ms	49292 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
//#include "grader.cpp" 

using namespace std ;

const int MAX = 17 ;
vector<int>a , b ;
long long dp[MAX][(1 << MAX)] ;
int n ;

long long solve(int idx , int mask)
{
	if(mask == (1 << n) - 1)
		return 0 ;
	long long &ret = dp[idx][mask] ;
	if(ret != -1)
		return ret ;
	ret = 1e12 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if((mask & (1 << i)))
			continue ;
		ret = min(ret , solve(i , mask | (1 << i)) + max(0ll , b[idx]*1ll - a[i]*1ll)) ;
	}
	return ret ;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	memset(dp , -1 , sizeof(dp)) ;
    n = (int) s.size();
    a = s , b = t ;
    long long ans = 1e18 ;
    for(int i = 0 ; i < n ; ++i)
    	ans = min(ans , solve(i , 1 << i)) ;
    return ans ;
}

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