Submission #69760

#	Time	Username	Problem	Language	Result	Execution time	Memory
69760		Noam527	Wiring (IOI17_wiring)	C++17	100 / 100	67 ms	69816 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199, inf = 1e16;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

ll min_total_length(vector<int> r, vector<int> b) {
	int n = r.size() + b.size();
	vector<int> a(n), col(n);
	vector<ll> dp(n);
	int p1 = 0, p2 = 0;
	while (p1 < r.size() && p2 < b.size()) {
		if (r[p1] < b[p2])
			a[p1 + p2] = r[p1], col[p1 + p2] = 0, p1++;
		else
			a[p1 + p2] = b[p2], col[p1 + p2] = 1, p2++;
	}
	while (p1 < r.size())
		a[p1 + p2] = r[p1], col[p1 + p2] = 0, p1++;
	while (p2 < b.size())
		a[p1 + p2] = b[p2], col[p1 + p2] = 1, p2++;

	vector<int> pos;
	pos.push_back(0);
	for (int i = 1; i < n; i++)
		if (col[i] != col[i - 1]) pos.push_back(i);
	for (int i = pos[0]; i < pos[1]; i++) dp[i] = inf;

	vector<ll> mn(n);
	ll curval;
	for (int ind = 1, S, T, nxt; ind < pos.size(); ind++) {
		S = pos[ind - 1];
		T = pos[ind];
		nxt = (ind + 1 < pos.size() ? pos[ind + 1] : n);
		// part 1
		curval = 0;
		for (int j = T - 1; j >= S; j--) {
			curval += a[T - 1] - a[j];
			if (j > 0)
				mn[j] = min(dp[j - 1], dp[j]) + curval;
			else
				mn[j] = curval;
			if (j + 1 < T) mn[j] = min(mn[j], mn[j + 1]);
		}
		curval = 0;
		for (int j = T; j < nxt; j++) {
			curval += a[j] - a[T - 1];
			dp[j] = curval + mn[max(S, 2 * T - j - 1)];
		}
		// part 2
		curval = 0;
		for (int j = S; j < T; j++)
			curval += a[T] - a[j];
		for (int j = S; j < T; j++) {
			if (j > 0)
				mn[j] = min(dp[j - 1], dp[j]) + curval;
			else
				mn[j] = curval;
			if (S < j) mn[j] = min(mn[j], mn[j - 1]);
			curval -= (a[T] - a[j]);
		}
		curval = 0;
		for (int j = T; j < nxt; j++) {
			curval += (a[j] - a[T]);
			if (S <= 2 * T - j - 1)
				dp[j] = min(dp[j], curval + mn[2 * T - j - 1]);
		}
	}
	return dp.back();
}
/*
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for (auto &i : a) cin >> i;
	for (auto &i : b) cin >> i;
	cout << min_total_length(a, b) << endl;
}
*/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (p1 < r.size() && p2 < b.size()) {
         ~~~^~~~~~~~~~
wiring.cpp:19:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (p1 < r.size() && p2 < b.size()) {
                          ~~~^~~~~~~~~~
wiring.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (p1 < r.size())
         ~~~^~~~~~~~~~
wiring.cpp:27:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (p2 < b.size())
         ~~~^~~~~~~~~~
wiring.cpp:38:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int ind = 1, S, T, nxt; ind < pos.size(); ind++) {
                               ~~~~^~~~~~~~~~~~
wiring.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   nxt = (ind + 1 < pos.size() ? pos[ind + 1] : n);
          ~~~~~~~~^~~~~~~~~~~~

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