Submission #286281

#	Time	Username	Problem	Language	Result	Execution time	Memory
286281		user202729	전선 연결 (IOI17_wiring)	C++17	13 / 100	35 ms	3840 KiB

wiring

// moreflags=grader.cpp
//
// 13
#include "wiring.h"
#include<vector>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<map>
#include<algorithm>


long long min_total_length(std::vector<int> red, std::vector<int> blue) {
	auto const distance=[&](int i, int j){ return std::abs(red[i]-blue[j]); };
	if(red.back()<=blue[0]){
		int64_t result{};
		if(red.size()<=blue.size())
			for(int i=0; i<(int)blue.size(); ++i)
				result+=distance(std::min((int)red.size()-1, i), i);
		else
			for(int i=0; i<(int)red.size(); ++i)
				result+=distance(i, std::max(0, i+(int)blue.size()-(int)red.size()));
		return result;
	}
	return -1; // subtask 2

	auto const nearest=[&](std::vector<int> const& first, std::vector<int> const& sec){
		auto iterator=sec.begin();
		std::vector<int> result; result.reserve(first.size());
		for(auto it: first){
			while(iterator!=sec.end() and *iterator<it) ++iterator;
			assert(iterator==std::lower_bound(begin(sec), end(sec), it));
			result.push_back(
					iterator==sec.begin() or (iterator!=sec.end() and *iterator-it<it-iterator[-1]) ?
					int(iterator-sec.begin()): int(iterator-sec.begin()-1)
					);
		}
		return result;
	};
	auto const redNear=nearest(red, blue);
	auto const blueNear=nearest(blue, red);

	std::vector<std::map<int, int64_t>> f(red.size());
	auto const optimize=[&](int i, int j, int64_t oldValue){
		int64_t const value=oldValue+distance(i, j);
		auto [iterator, inserted]=f[i].insert({j, value});
		if(not inserted) iterator->second=std::min(iterator->second, value);
	};
	optimize(0, 0, 0);

	for(int i=0; i<(int)red.size(); ++i){
#if not LOCAL
		if(i!=0) f[i-1].clear();
#endif

		for(auto [j, value]: f[i]){
			bool const imaximum=i==(int)red.size()-1, jmaximum=j==(int)blue.size()-1;
			if(imaximum and jmaximum)
				return value;

			if(not imaximum){
				if(not jmaximum)
					if(distance(i, redNear[i])+distance(blueNear[j], j)>distance(i, j))
						optimize(i+1, j+1, value);
				if(redNear[i]==j and redNear[i+1]==j)
					optimize(i+1, j, value);
			}
			if(not jmaximum)
				if(blueNear[j]==i and blueNear[j+1]==i)
					optimize(i, j+1, value); // map doesn't invalidate iterators
		}
	}

	assert(false); __builtin_unreachable();
}

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45