제출 #286264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286264		user202729	전선 연결 (IOI17_wiring)	C++17	7 / 100	1093 ms	9592 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 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+std::abs(red[i]-blue[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(i!=0) f[i-1].clear();

		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)
					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: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45