제출 #50266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50266		Bruteforceman	전선 연결 (IOI17_wiring)	C++11	100 / 100	115 ms	123848 KiB

wiring

#include "bits/stdc++.h"
#include "wiring.h"
using namespace std;
const long long inf = 1e15;

vector <long long> dp[200010];
vector <int> group[200010];
vector <long long> first[200010], last[200010];
typedef pair <int, int> pii;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int g = 0;
	int n = r.size();
	int m = b.size();
	vector <pii> v;
	for(int i = 0; i < n; i++) {
		v.emplace_back(r[i], 0);
	}
	for(int i = 0; i < m; i++) {
		v.emplace_back(b[i], 1);
	}
	sort(v.begin(), v.end());
	int prevc = -1;
	group[0].push_back(-1);
	for(int i = 0; i < n+m; i++) {
		if(prevc == v[i].second) {
			group[g].push_back(v[i].first);
		} else {
			++g;
			prevc = v[i].second;
			group[g].push_back(-1);
			group[g].push_back(v[i].first);
		}
	}
	for(int i = 0; i <= g; i++) {
		int sz = group[i].size() - 1;
		first[i].resize(sz + 1);
		last[i].resize(sz + 1);
		for(int j = 1; j <= sz; j++) {
			first[i][j] = first[i][j - 1] + group[i][j];
			last[i][j] = last[i][j - 1] + group[i][sz - j + 1];
		}
	}
	for(int i = 1; i <= g+1; i++) {
		int sz = group[i - 1].size() - 1;
		dp[i].resize(sz + 1);
		for(int j = 0; j <= sz; j++) {
			dp[i][j] = inf;
		}
	}
	dp[1][0] = 0;
	for(int i = 1; i <= g; i++) {
		int sz_prev = group[i - 1].size() - 1;
		int sz_cur = group[i].size() - 1;
		for(int j = sz_prev; j > 0; j--) {
			dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + abs(group[i - 1][sz_prev - j + 1] - group[i][1]));
		}
		for(int j = 0; j <= min(sz_cur, sz_prev); j++) {
			dp[i + 1][sz_cur - j] = min(dp[i + 1][sz_cur - j], dp[i][j] + abs(last[i - 1][j] - first[i][j]));
		}
		for(int j = sz_cur; j > 0; j--) {
			if(i == 1) break;
			dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i + 1][j] + abs(group[i][sz_cur - j + 1] - group[i - 1].back()));
		}
	}
	return dp[g + 1][0];
}

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