Submission #465478

#	Time	Username	Problem	Language	Result	Execution time	Memory
465478		flappybird	Wiring (IOI17_wiring)	C++14	100 / 100	282 ms	38392 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define MAX 401010
#define INF 10101010101010
vector<ll> R, B;
ll N, M;
ll dp[MAX], near[MAX], pv[MAX], sum[MAX];
vector<pair<ll, ll>> point;

long long min_total_length(vector<int> r, vector<int> b) {
	ll i, j;
	N = r.size();
	M = b.size();
	ll P = N + M;
	point.push_back({ 0, 0 });
	for (i = 0; i < N; i++) point.push_back({ (ll)r[i], 0 });
	for (i = 0; i < M; i++) point.push_back({ (ll)b[i], 1 });
	sort(point.begin() + 1, point.end());
	dp[1] = INF;
	vector<ll> last(2);
	for (i = 1; i <= P; i++) near[i] = 101010101010;
	for (i = 1; i <= P; i++) {
		if (last[!point[i].second]) near[i] = min(near[i], abs(point[i].first - point[last[!point[i].second]].first));
		last[point[i].second] = i;
	}
	last[0] = last[1] = 0;
	for (i = P; i >= 1; i--) {
		if (last[!point[i].second]) near[i] = min(near[i], abs(point[i].first - point[last[!point[i].second]].first));
		last[point[i].second] = i;
	}
	map<ll, ll> mp;
	ll cnt = 0;
	for (i = -P; i <= P; i++) mp[i] = -1;
	mp[0] = 0;
	for (i = 1; i <= P; i++) {
		if (point[i].second) cnt++, sum[i] = sum[i - 1] + point[i].first;
		else cnt--, sum[i] = sum[i - 1] - point[i].first;
		if (mp[cnt] >= 0) pv[i] = mp[cnt];
		else pv[i] = -1;
		mp[cnt] = i;
	}
	for (i = 1; i <= P; i++) {
		dp[i] = dp[i - 1] + near[i];
		if (pv[i] >= 0) dp[i] = min(dp[i], dp[pv[i]] + abs(sum[i] - sum[pv[i]]));
	}
	return dp[P];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:15:8: warning: unused variable 'j' [-Wunused-variable]
   15 |  ll i, j;
      |        ^

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