제출 #371263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371263		KoD	전선 연결 (IOI17_wiring)	C++17	100 / 100	47 ms	7912 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

template <class T>
using Vec = std::vector<T>;
using ll = long long;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

ll min_total_length(Vec<int> r, Vec<int> b) {
	Vec<Vec<int>> component;
	const int n = (int) r.size();
	const int m = (int) b.size();
	{
		int last = -1;
		int i = 0, j = 0;
		while (i != n || j != m) {
			if ((j == m) || (i != n && r[i] < b[j])) {
				if (last != 0) {
					component.push_back({ });
					last = 0;
				}
				component.back().push_back(r[i]);
				i += 1;
			}
			else {
				if (last != 1) {
					component.push_back({ });
					last = 1;
				}
				component.back().push_back(b[j]);
				j += 1;
			}
		}
	}
	Vec<ll> dp(component[0].size() + 1, INF);
	{
		ll sum = 0;
		for (const auto x: component[0]) {
			sum += component[0].back() - x;
		}
		dp.back() = sum;
	}
	for (int i = 1; i < (int) component.size(); ++i) {
		const ll dif = component[i].front() - component[i - 1].back();
		Vec<ll> left_min(dp.size() + 1, INF);
		for (int j = 0; j < (int) dp.size(); ++j) {
			left_min[j + 1] = left_min[j];
			left_min[j + 1] = std::min(left_min[j + 1], dp[j]);
		}
		Vec<ll> right_min(dp.size() + 1, INF);
		for (int j = (int) dp.size() - 1; j >= 0; --j) {
			right_min[j] = right_min[j + 1];
			right_min[j] = std::min(right_min[j], dp[j] + dif * j);
		}
		const auto cost = [&](const int k) {
			const int l = (int) component[i].size() - k;
			ll ret = left_min[std::min((int) left_min.size() - 1, l)] + dif * l;
			if (l < right_min.size()) {
				ret = std::min(ret, right_min[l]);
			}
			return ret;
		};
		dp.resize(component[i].size() + 1, INF);
		ll sum = 0;
		for (const auto x: component[i]) {
			sum += x - component[i].front();
		}
		dp[0] = cost(0) + sum;
		for (int j = (int) component[i].size() - 1; j >= 0; --j) {
			const int r = (int) component[i].size() - j;
			sum -= component[i][j] - component[i].front();
			sum += component[i].back() - component[i][j];
			dp[r] = cost(r) + sum;
		}
	}
	return dp[0];
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In lambda function:
wiring.cpp:59:10: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if (l < right_min.size()) {
      |        ~~^~~~~~~~~~~~~~~~~~

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