Submission #1321080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321080		kasamchi	전선 연결 (IOI17_wiring)	C++20	30 / 100	1094 ms	8376 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];
	}

	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 psz = prb - plb + 1;

		vector<long long> dqb(psz);
		for (int i = 0, p = plb; i < psz; i++, p++) {
			dqb[i] += min(dp[p - 1], dp[p]);
			dqb[i] += pre[p - 1] - pre[plb - 1];
		}

		vector<long long> dqd(psz);
		dqd[0] = dqb[0];
		for (int i = 1; i < psz; i++) {
			dqd[i] = -dqb[i - 1] + dqb[i];
		}

		for (int c = clb; c <= crb; c++) {
			int 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);
			}

			if (sid == 1) {
				dp[c] = sum;
			} else {
				vector<pair<int, long long>> ops;
				dqd[0] += sum, ops.push_back(make_pair(0, sum));
				for (int i = 1; i <= psz - csz; i++) {
					dqd[i] -= pos[clb], ops.push_back(make_pair(i, -pos[clb]));
				}
				for (int i = max(0, psz - csz) + 1; i < psz; i++) {
					dqd[i] -= pos[prb], ops.push_back(make_pair(i, -pos[prb]));
				}

				long long cur = 0;
				vector<long long> dq(psz);
				for (int i = 0; i < psz; i++) {
					cur += dqd[i];
					dp[c] = min(dp[c], cur);
				}

				for (auto &[pos, val] : ops) {
					dqd[pos] -= val;
				}
			}
		}
	}
	return dp[N];
}

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