Submission #352761

#	Time	Username	Problem	Language	Result	Execution time	Memory
352761		tengiz05	Roller Coaster Railroad (IOI16_railroad)	C++17	11 / 100	2079 ms	10348 KiB

railroad

#include "railroad.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> s, t;
ll cost[18][18];
ll ans, sum;
bool used[18];
void rec(int i, int etap){
	if(sum >= ans)return;
	if(etap == n){
		ans = min(ans, sum);
		return;
	}
	for(int j=0;j<n;j++){
		if(used[j])continue;
		sum += max(0, t[i] - s[j]);
		used[j] = true;
		rec(j, etap+1);
		used[j] = false;
		sum -= max(0, t[i] - s[j]);
	}
	return;
}
ll plan_roller_coaster(vector<int> sk, vector<int> tk) {
	s = sk, t = tk;
	n = s.size();
	ans = 1e18;
	for(int j=0;j<n;j++){
		used[j] = true;
		rec(j,1);
		used[j] = false;
	}
	return ans;
}

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