Submission #958831

#	Time	Username	Problem	Language	Result	Execution time	Memory
958831		MinaRagy06	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	2036 ms	17808 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

ll plan_roller_coaster(vector<int> in, vector<int> out) {
	int n = in.size();
	set<array<int, 2>> s;
	for (int i = 0; i < n; i++) {
		s.insert({in[i], out[i]});
	}
	vector<array<int, 2>> a;
	while (s.size()) {
		array<int, 2> val = *s.begin();
		s.erase(s.begin());
		int st = val[0];
		while (1) {
			auto it = s.lower_bound({val[1], 0});
			if (it == s.end()) {
				break;
			}
			val = *it;
			s.erase(it);
		}
		int en = val[1];
		a.push_back({st, en});
	}
	n = a.size();
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i][1] - a[i][0];
	}
	if (n == 1) {
		return 0;
	}
	ll ans = 1e18;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) {
			if (x == y) continue;
			ans = min(ans, sum + a[x][0] - a[y][1]);
		}
	}
	return ans;
}

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