Submission #798014

#	Time	Username	Problem	Language	Result	Execution time	Memory
798014		LittleCube	Wiring (IOI17_wiring)	C++17	17 / 100	1074 ms	10068 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

ll cost(ll x, ll y)
{
	return abs(x - y);
}

vector<ll> trans(vector<ll> l, vector<ll> ldp, vector<ll> r)
{
	// cerr << ' ';
	// for (ll i : l)
	// 	cerr << i << ' ';
	// cerr << "->";
	// for (ll i : r)
	// 	cerr << ' ' << i;
	// cerr << '\n';
	
	// for (ll i : ldp)
	// 	cerr << i << ' ';
	// cerr << '\n';

	int n = l.size(), m = r.size();
	ll small = r[0], large = l.back();
	vector<ll> rdp(m + 1, 1e18);
	reverse(ldp.begin(), ldp.end());
	reverse(l.begin(), l.end());
	l.insert(l.begin(), 0);
	r.insert(r.begin(), 0);
	{
		ll sum = 0;
		for (auto &i : l)
			i = (sum += i);
	}
	{
		ll sum = 0;
		for (auto &i : r)
			i = (sum += i);
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (i <= j)
				rdp[j] = min(rdp[j], r[j] - l[i] - large * (j - i) + ldp[i]);
			else
				rdp[j] = min(rdp[j], r[j] + small * (i - j) - l[i] + ldp[i]);
	return rdp;
}

long long min_total_length(vector<int> r, vector<int> b)
{
	if (r[0] > b[0])
		r.swap(b);
	vector<pii> l;
	for (auto i : r)
		l.emplace_back(pii(i, 1));
	for (auto i : b)
		l.emplace_back(pii(i, 2));
	sort(l.begin(), l.end());
	vector<ll> pre, pdp;
	pdp.emplace_back(0);
	int last = 1, i = 0;
	while (i < l.size() && l[i].S == last)
	{
		pre.emplace_back(l[i].F);
		pdp.emplace_back(1e18);
		i++;
	}
	while (i < l.size())
	{
		last ^= 3;
		vector<ll> cur;
		while (i < l.size() && l[i].S == last)
		{
			cur.emplace_back(l[i].F);
			i++;
		}
		pdp = trans(pre, pdp, cur);
		pre = cur;
	}
	return pdp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  while (i < l.size() && l[i].S == last)
      |         ~~^~~~~~~~~~
wiring.cpp:73:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  while (i < l.size())
      |         ~~^~~~~~~~~~
wiring.cpp:77:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   while (i < l.size() && l[i].S == last)
      |          ~~^~~~~~~~~~

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