Submission #492051

#	Time	Username	Problem	Language	Result	Execution time	Memory
492051		Virv	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	384 ms	20244 KiB

railroad

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

#include "railroad.h"

long long f(std::vector<int> const &s, std::vector<int> const &t) {
	std::set<std::pair<int, int>> w;
	for (size_t i{}; i < s.size(); ++i) w.emplace(s[i], t[i]);

	std::vector<std::pair<int, int>> v;
	v.push_back(*w.begin());
	w.erase(w.begin());

	while (!w.empty()) {
		auto it = w.lower_bound({v.back().second, v.back().first});
		if (it == w.end()) --it;
		v.push_back(*it);
		w.erase(it);
	}

	// for (auto [a, b] : v) std::cerr << a << ' ' << b << '\n';

	long long R{};
	for (size_t i{}; i + 1 < v.size(); ++i) R += std::max(0, v[i].second - v[i + 1].first);
	// std::cerr << R << '\n';
	return R;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
	auto a = f(s, t);
	for (size_t i{}; i < s.size(); ++i) {
		std::swap(s[i], t[i]);
		s[i] *= -1;
		t[i] *= -1;
	}
	auto b = f(s, t);
	return std::min(a, b);
}

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