Submission #55489

#	Time	Username	Problem	Language	Result	Execution time	Memory
55489		minkank	Wiring (IOI17_wiring)	C++17	100 / 100	108 ms	92580 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

typedef pair<int, int> ii;
#define x first
#define y second

void upd(long long &x, long long y) {
	x = min(x, y);
}

long long min_total_length(vector<int> r, vector<int> b) {
	vector<ii> all;
	for(int i = 0; i < r.size(); ++i)
		all.push_back(ii(r[i], 0));
	for(int i = 0; i < b.size(); ++i)
		all.push_back(ii(b[i], 1));
	sort(all.begin(), all.end());
	vector<long long> sum;
	for(int i = 0; i < all.size(); ++i) {
		sum.push_back(all[i].x);
		if(i) sum[i] += sum[i - 1];
	}
	vector<int> sz; 
	vector<vector<long long> > f;
	for(int i = 0; i < all.size(); ++i) {
		sz.push_back(1);
		while(i + 1 < all.size() && all[i].y == all[i + 1].y) {
			i++;
			sz[sz.size() - 1]++;
		}
		f.push_back(vector<long long>(sz.back() + 5, 1e18));
	}
	f.push_back(vector<long long>(1, 1e18));
	f[0][0] = 0;
	int cur = 0;
	for(int i = 0; i < sz.size(); ++i) {
		for(int j = 0; j < sz[i]; ++j) {
			if(cur - j - 1 >= 0) {
				upd(f[i][j + 1], f[i][j] + all[cur].x - all[cur - j - 1].x);
			}
			if(i != sz.size() - 1) {
				upd(f[i][j + 1], f[i][j] + all[cur - j + sz[i]].x - all[cur].x);
				if(sz[i] - j <= sz[i + 1]) {
					long long sumL = sum[cur - j + sz[i] - 1];
					if(cur) sumL -= sum[cur - 1];
					long long sumR = sum[cur - j + sz[i] + sz[i] - j - 1];
					sumR -= sum[cur - j + sz[i] - 1];
					upd(f[i + 1][sz[i] - j], f[i][j] + sumR - sumL);
				}
			}
			cur++;
		}
		upd(f[i + 1][0], f[i][sz[i]]);
	}
	return f[sz.size()][0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < r.size(); ++i)
                 ~~^~~~~~~~~~
wiring.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < b.size(); ++i)
                 ~~^~~~~~~~~~
wiring.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < all.size(); ++i) {
                 ~~^~~~~~~~~~~~
wiring.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < all.size(); ++i) {
                 ~~^~~~~~~~~~~~
wiring.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i + 1 < all.size() && all[i].y == all[i + 1].y) {
         ~~~~~~^~~~~~~~~~~~
wiring.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < sz.size(); ++i) {
                 ~~^~~~~~~~~~~
wiring.cpp:44:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i != sz.size() - 1) {
       ~~^~~~~~~~~~~~~~~~

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