제출 #1321000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321000		kasamchi	전선 연결 (IOI17_wiring)	C++20	30 / 100	1034 ms	7608 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

long long min_total_length(vector<int> r, vector<int> b) {
	int N = r.size() + b.size();
	int ridx = 0, bidx = 0;
	vector<int> pos = {0}, col = {0};
	while (ridx < r.size() || bidx < b.size()) {
		if (bidx == b.size()) {
			pos.push_back(r[ridx]);
			col.push_back(0);
			ridx++;
		} else if (ridx == r.size()) {
			pos.push_back(b[bidx]);
			col.push_back(1);
			bidx++;
		} else if (r[ridx] < b[bidx]) {
			pos.push_back(r[ridx]);
			col.push_back(0);
			ridx++;
		} else {
			pos.push_back(b[bidx]);
			col.push_back(1);
			bidx++;
		}
	}

	vector<pair<int, int>> seg;
	for (int i = 1; i <= N; ) {
		int j = i;
		while (j <= N && col[i] == col[j]) {
			j++;
		}
		seg.push_back(make_pair(i, j - 1));
		i = j;
	}

	vector<long long> pre(N + 1);
	for (int i = 1; i <= N; i++) {
		pre[i] = pre[i - 1] + pos[i];
	}

	for (int i = 0; i < seg[1].first - seg[0].first; i++) {
		// cerr << "   ";
	}

	vector<long long> dp(N + 1, (long long)1e18);
	for (int sid = 1; sid < seg.size(); sid++) {
		int clb = seg[sid].first, crb = seg[sid].second;
		int plb = seg[sid - 1].first, prb = seg[sid - 1].second;

		int opt = prb;
		for (int c = clb; c <= crb; c++) {
			int psz = prb - plb + 1, csz = c - clb + 1;
			long long sum = 0;
			sum += pre[c] - pre[clb - 1];
			sum -= pre[prb] - pre[plb - 1];
			if (psz <= csz) {
				sum -= (long long)pos[prb] * (csz - psz);
			} else {
				sum += (long long)pos[clb] * (psz - csz);
			}

			int bst = plb;
			for (int p = plb; p <= opt; p++) {
				int i = p - plb;
				long long cur = (sid == 1 ? 0 : min(dp[p - 1], dp[p]));
				if (cur + sum < dp[c]) {
					bst = p;
				}
				dp[c] = min(dp[c], cur + sum);
				sum += pos[plb + i];
				if (psz - i > csz) {
					sum -= pos[clb];
				} else {
					sum -= pos[prb];
				}
				if (sid == 1) {
					break;
				}
			}
			opt = bst;
			// cerr << setw(2) << opt << ' ';
		}
	}
	// // cerr << '\n';
	for (int i = 1; i <= N; i++) {
		// cerr << ' ' << col[i] << ' ';
	}
	// cerr << '\n';
	for (int i = 1; i <= N; i++) {
		if (dp[i] == 1e18) {
			// cerr << "-1 ";
		} else {
			// cerr << setw(2) << dp[i] << ' ';
		}
	}
	// cerr << "\n---\n";
	return dp[N];
}

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