제출 #272916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
272916		mjkocijan	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	587 ms	32468 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;

multiset<ii> e;
multiset<int> haha;
ll reza = 0;
ll pa = 0;
ll lst = -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 < n; i++) {
  	if (s[i] == t[i]) {
  		e.insert({s[i], 3});
  	}
  	if (s[i] < t[i]) {
  		//e.insert({s[i], 4});
  		e.insert({s[i], 10 + t[i]});
  		e.insert({t[i], 2});
  	}
  	if (s[i] > t[i]) {
  		e.insert({s[i], 1});
  		e.insert({t[i], 5});
  	}
  }
  
  while (!e.empty()) {
  	ii cu = *e.begin();
  	e.erase(e.begin());
  	
  	if (cu.Y == 1) {
  		pa++;
  	}
  	if (cu.Y == 2) {
  		pa--;
  		haha.erase(cu.X);
  	}
  	if (cu.Y == 3) {
  		while (pa > 0) {
  			pa--;
  			reza += ll((*haha.begin()) - cu.X);
  			haha.erase(haha.begin());
  		}
  	}
  	/*if (cu.Y == 4) {
  		pa++;
  		haha.insert();
  	}*/
  	if (cu.Y > 9) {
  		pa++;
  		haha.insert(cu.Y - 10);
  		lst = cu.X;
  	}
  	if (cu.Y == 5) {
  		pa--;
  		lst = cu.X;
  	}
  	
  	if (e.empty() || (*e.begin()).X == cu.X) continue;
  	
  	while (pa > 1) {
  		pa--;
  		reza += ll((*haha.begin()) - cu.X);
  		haha.erase(haha.begin());
  	}
  }
  
  return reza;
  
  /*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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36