Submission #265502

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

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
#define MAXN 18
#define LOG 20
#define INF 1001001001001001001LL

ll dp[1 << MAXN][LOG], reza = INF;

//set<ii> v;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  int n = (int) s.size();
  
  for (int i = 0; i < (1 << n); i++)
  	for (int j = 0; j < n; j++)
  		dp[i][j] = INF;
  		
  for (int i = 0; i < n; i++)
  	dp[1 << i][i] = 0;
  	
  for (int i = 1; i < (1 << n); i++) {
  	if (__builtin_popcount(i) == 1) continue;
  	for (int j = 0; j < n; j++) {
  		if (i & (1 << j)) {
  			for (int k = 0; k < n; k++) {
  				if (!(i & (1 << k)) || j == k) continue;
  				
  				dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + (ll)max(0, t[k] - s[j]));
  			}
  			
  			if (i == (1 << n) - 1) {
  				reza = min(reza, dp[i][j]);
  			}
  		}
  	}
  }
  return reza;
  /*for (int i = 0; i < n; i++) {
  	v.insert({s[i], t[i]});
  	//cout << t[i]<<' '<<s[i]<<endl;
  }
  ll ri = 1;
	while (!v.empty()) {
		auto cu = v.lower_bound({ri, 0});
		if (cu == v.end()) return 1;
		ri = cu -> Y;
		v.erase(cu);
		cout << cu -> X <<' '<<cu -> Y<<endl;
	}
  return 0;*/
}

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