Submission #826462

#	Time	Username	Problem	Language	Result	Execution time	Memory
826462		caganyanmaz	Wiring (IOI17_wiring)	C++17	30 / 100	796 ms	5460 KiB

wiring

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
using namespace std;
#include "wiring.h"

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif


constexpr static int MXN = 1e5;
#ifdef DEBUGGING
constexpr static int MXG = 10;
#else
constexpr static int MXG = 205;
#endif
constexpr static int INF = 1e10;
deque<int> r, b;



long long subtask2()
{
	int m = r.back();
	int sum = 0;
	for (int i : r)
		sum += m - i;
	for (int i : b)
		sum += i - m;
	if (r.size() > b.size())
		sum += (b[0] - m) * (r.size() - b.size());
	return sum;
}

vector<int> dp(MXG);
vector<int> dp2(MXG);

long long min_total_length(vector<int32_t> rr, vector<int32_t> bb) 
{
	for (int i : rr)
		r.push_back(i);
	for (int i : bb)
		b.push_back(i);
	if (r.back() < b[0])
		return subtask2();
	int g = 200;
	if (rr.size() > 200 || bb.size() > 200)
		g = 9;
	int current = 0;
	fill(dp.begin(), dp.begin() + g, INF);
	dp[0] = 0;
	if (r[0] > b[0])
		swap(r, b);
	int mnr = -INF;
	while (r.size() || b.size())
	{
		vector<int> v;
		assert(v.size() < g);
		while (r.size() && (b.empty() || r[0] < b[0])) 
		{
			v.pb(r[0]);
			r.pop_front();
		}
		fill(dp2.begin(), dp2.begin() + g, INF);
		int rb = b[0], lb = v[0];
		for (int i = 0; i <= v.size(); i++) // How many we're putting to right
		{
			int lsum = 0;
			int rsum = 0;
			for (int j = 0; j < v.size()-i; j++)
				lsum += v[j] - lb;
			for (int j = v.size()-i; j < v.size(); j++)
				rsum += rb - v[j];
			for (int j = 0; j < g; j++) // How many is coming from right
			{
				if (j < v.size()-i) // We need to take more
					dp2[i] = min<int>(dp2[i], dp[j] + (v.size()-i-j) * (lb - mnr) + lsum + rsum);
				else
					dp2[i] = min<int>(dp2[i], dp[j] + lsum + rsum);
				// We might need to give more as well (but it has 0 contribution so it doesn't matter)
			}

		}
		for (int i = 0; i < g; i++)
			dp[i] = dp2[i];
		mnr = v.back();
		swap(r, b);
	}
	return dp[0];
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from wiring.cpp:1:
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:61:19: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   61 |   assert(v.size() < g);
      |          ~~~~~~~~~^~~
wiring.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i = 0; i <= v.size(); i++) // How many we're putting to right
      |                   ~~^~~~~~~~~~~
wiring.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   73 |    for (int j = 0; j < v.size()-i; j++)
      |                    ~~^~~~~~~~~~~~
wiring.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for (int j = v.size()-i; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
wiring.cpp:79:11: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   79 |     if (j < v.size()-i) // We need to take more
      |         ~~^~~~~~~~~~~~
wiring.cpp:52:6: warning: unused variable 'current' [-Wunused-variable]
   52 |  int current = 0;
      |      ^~~~~~~

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