Submission #114605

#	Time	Username	Problem	Language	Result	Execution time	Memory
114605		davitmarg	Roller Coaster Railroad (IOI16_railroad)	C++17	34 / 100	67 ms	10652 KiB

railroad

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;
int n;
LL dp[(1<<16)+4][16+4],ans=mod*mod;
vector<int> s,t;

int Main()
{
	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j <= n; j++)
			dp[i][j] = mod*mod;
	for (int j = 0; j < n; j++)
		dp[1 << j][j] = 0;
	for (int mask = 1; mask < (1 << n); mask++)
		for (int j = 0; j < n; j++)
			if (((1 << j) & mask))
				for (int i = 0; i < n; i++)
					if (!((1 << i) & mask))
						dp[mask | (1 << i)][i] = min(dp[mask | (1 << i)][i], max(t[j] - s[i], 0) + dp[mask][j]);

	for (int j = 0; j < n; j++)
		ans = min(ans, dp[(1 << n) - 1][j]);
	return 0;
}

LL plan_roller_coaster(vector<int> S, vector<int> T)
{
	n = S.size();
	s = S;
	t = T;
	Main();
	return ans;
}

#ifdef death

int main()
{
	int N;
	vector<int> S,T;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		S.PB(0);
		cin >> S.back();
		T.PB(0);
		cin >> T.back();
	}
	cout << plan_roller_coaster(S,T) << endl;
	return 0;
}

#endif 


/*



*/

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