제출 #50989

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

wiring

#include "wiring.h"
#include <algorithm>

using namespace std;
typedef long long llong;

const int R = 0, B = 1;
const int inf = 1e9 + 7;
int n, m;
struct point {
	int x, k;
	bool operator<(const point &p) const {
		return x < p.x;
	}
};

point ps[200001];
llong sum[200001];
llong dp[200001];
llong min_total_length(vector<int> r, vector<int> b) {
	n = r.size();
	m = b.size();
	int i = 0, j = 0, p = 0;
	while (i < n && j < m) {
		if (r[i] < b[j]) ps[++p] = { r[i++], R };
		else ps[++p] = { b[j++], B };
	}
	while (i < n) ps[++p] = { r[i++], R };
	while (j < m) ps[++p] = { b[j++], B };
	int rd = -inf, bd = -inf, nc = 0, pc = 0, c = -1;
	r.push_back(inf << 1);
	b.push_back(inf << 1);
	for (p = 1, i = j = 0; p <= n + m; ++p) {
		int x = ps[p].x, k = ps[p].k;
        if (k != c) {
            c = k;
            pc = nc;
            nc = 0;
        }
        ++nc;
		
		sum[p] = sum[p - 1] + (k == R ? -x : x);
		if (k == B) {
			while (i < n && r[i] <= x) ++i;
			dp[p] = dp[p - 1] + min(x - rd, r[i] - x);
		}
		else {
			while (j < m && b[j] <= x) ++j;
			dp[p] = dp[p - 1] + min(x - bd, b[j] - x);
		}

		if (nc <= pc) {
            int t = p - (nc << 1);
            dp[p] = min(dp[p], dp[t] + abs(sum[p] - sum[t]));
		}

		if (k == R) rd = x;
		else bd = x;
	}
	return dp[n + m];
}

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