Submission #117115

#	Time	Username	Problem	Language	Result	Execution time	Memory
117115		Lawliet	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	84 ms	31112 KiB

railroad

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

#define MAX 20
#define EXP 1024*64 + 10
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;

int N;

int S[MAX];
int T[MAX];

lli dp[MAX][EXP];

bool isActive(int i, int mask) { return mask & (1 << i); }

lli cost(int i, int j)//estou no i e vou entrar no j
{
	if(S[j] >= T[i]) return 0;
	return T[i] - S[j];
}

lli DP(int i, int mask)
{
	//printf("i = %d   ask = %d\n",i,mask);
	if(dp[i][mask] != -1) return dp[i][mask];

	if(mask == (1 << i)) return dp[i][mask] = 0;

	dp[i][mask] = INF;

	for(int g = 0 ; g < N ; g++)
	{
		if(!isActive(g , mask) || g == i) continue;

		dp[i][mask] = min(dp[i][mask] , DP(g , mask - (1 << i)) + cost(g , i));
	}

	//printf("dp(%d,%d) = %lld\n",i,mask,dp[i][mask]);

	return dp[i][mask];
}

long long int plan_roller_coaster(std::vector<int> s, std::vector<int> t)
{
	N = s.size();

	memset(dp , -1 , sizeof(dp));

	for(int g = 0 ; g < N ; g++)
	{
		S[g] = s[g];
		T[g] = t[g];	
	}

	lli ans = INF;

	for(int g = 0 ; g < N ; g++)
		ans = min(ans , DP(g , (1 << N) - 1));

	return ans;
}

/*int main()
{
	scanf("%d",&N);

	vector<int> ss(N), tt(N);

	for(int g = 0 ; g < N ; g++)
		scanf("%d",&ss[g]);

	for(int g = 0 ; g < N ; g++)
		scanf("%d",&tt[g]);

	printf("%lld\n",plan_roller_coaster(ss , tt));
}*/

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