Submission #352609

#	Time	Username	Problem	Language	Result	Execution time	Memory
352609		amunduzbaev	Roller Coaster Railroad (IOI16_railroad)	C++14	11 / 100	2073 ms	524292 KiB

railroad

#include "railroad.h"

#ifndef EVAL
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
const ll inf = 1e18+7;

vii s, t;
int n;
ll mn;

void check(vii tt){
	ll cost = 0;
	//for(int i=0;i<n;i++) cout<<s[tt[i]]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<t[tt[i]]<<" ";
	//cout<<"\n";
	//cout<<cost<<"\n";
	for(int i=0;i<n-1;i++){
		if(t[tt[i]] < s[tt[i+1]]) continue;
		//cout<<t[tt[i]]<<" "<<s[tt[i]]<<"\n";
		cost += (ll)(t[tt[i]] - s[tt[i+1]]);
	}umin(mn, cost);
}

void  find(vii used, vii way){
	if(sz(way) == n){check(way);}
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		used[i] = 1;
		way.pb(i);
		find(used, way);
		used[i] = 0;
		way.pop_back();
	}
}

long long plan_roller_coaster(vector<int> S, vector<int> T) {
	n = sz(S);
	s.resize(n);
	t.resize(n);
	//for(int i=0;i<n;i++) cout<<S[i]<<" ";
	//cout<<"\n";
	//for(int i=0;i<n;i++) cout<<T[i]<<" ";
	//cout<<"\n";
	
	for(int i=0;i<n;i++) s[i] = S[i];
	for(int i=0;i<n;i++) t[i] = T[i];
	mn = inf;
	find(vii(n, 0), {});
	return mn;
}

/*

4
1 7
4 3
5 8
6 6

*/

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