제출 #730327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730327		ktkerem	Roller Coaster Railroad (IOI16_railroad)	C++17	11 / 100	1659 ms	4204 KiB

railroad

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long int64;

int64 plan_roller_coaster(vector<int> s, vector<int> t) {
	int n = (int) s.size();
	vector<int> data(n);
	forn(i, n)
		data[i] = i;
	int64 res = 4e18;
	auto relax = [&]() {
	    int64 tmp = 0;
		for (int i = 1; i < n; ++i) {
			tmp += max(0, t[data[i - 1]] - s[data[i]]);
		}
		res = min(res, tmp);
	};
	auto test = [&]( bool reversed, function<long double(int)> f ) {
		sort(data.begin(), data.end(), [&](int i, int j){ return f(i) < f(j); });
		if (reversed)
			reverse(data.begin(), data.end());
		relax();
	};
	forn(reversed, 2) {
		test(reversed, [&]( int i ) { return s[i]; });
		test(reversed, [&]( int i ) { return t[i]; });
		test(reversed, [&]( int i ) { return s[i] + t[i]; });
		test(reversed, [&]( int i ) { return s[i] - t[i]; });
		test(reversed, [&]( int i ) { return (long double)s[i] * t[i]; });
		test(reversed, [&]( int i ) { return (long double)s[i] / t[i]; });
		test(reversed, [&]( int i ) { return (long double)s[i] * s[i] + (long double)t[i] * t[i]; });
		test(reversed, [&]( int i ) { return (long double)s[i] * s[i] - (long double)t[i] * t[i]; });
	}
	forn(it, (int) (1e7 / n)) {
	    random_shuffle(data.begin(), data.end());
	    relax();
	}
	return res;
}

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