Submission #1072509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072509		ArthuroWich	Wiring (IOI17_wiring)	C++17	0 / 100	1094 ms	7032 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int calc(vector<int> &r, vector<int> &b) {
	int ans = 0, rbe, bbe;
	sort(r.rbegin(), r.rend());
	sort(b.begin(), b.end());
	rbe = r.front();
	bbe = b.front();
	for (int i = 0; i < min((int) r.size(), (int) b.size()); i++) {
		ans += abs(b[i]-r[i]);
	}
	if (r.size() < b.size()) {
		for (int i = r.size(); i < b.size(); i++) {
			ans += abs(rbe-b[i]);
		}
	} else {
		for (int i = b.size(); i < r.size(); i++) {
			ans += abs(bbe-r[i]);
		}
	}
	return ans;
}
int min_total_length(vector<int32_t> r, vector<int32_t> b) {
	int n = r.size()+b.size();
	vector<pair<int, int>> a;
	for (int i = 0; i < r.size(); i++) {
		a.push_back({r[i], 0});
	}
	for (int i = 0; i < b.size(); i++) {
		a.push_back({b[i], 1});
	}
	vector<int> dp(n, INT64_MAX);
	sort(a.begin(), a.end());
	for (int i = 1; i < n; i++) {
		int l = -1, r = i;
		vector<int> lv, rv;
		for (int j = i; j >= 0; j--) {
			if (a[j].second != a[r].second) {
				l = j;
				break;
			} else {
				rv.push_back(a[j].first);
			}
		}
		if (l == -1) {
			continue;
		}
		for (int j = l; j >= 0; j--) {
			if (a[j].second == a[l].second) {
				lv.push_back(a[j].first);
				if (j-1 >= 0) {
					if (dp[j-1] == INT64_MAX) {
						continue;
					}
					dp[i] = min(dp[i], dp[j-1]+calc(lv, rv));
				} else if (j == 0) {
					dp[i] = min(dp[i], calc(lv, rv));
				}
			} else {
				break;
			}
		}
	}
	return dp[n-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int calc(std::vector<long long int>&, std::vector<long long int>&)':
wiring.cpp:15:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (int i = r.size(); i < b.size(); i++) {
      |                          ~~^~~~~~~~~~
wiring.cpp:19:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int i = b.size(); i < r.size(); i++) {
      |                          ~~^~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:28:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < r.size(); i++) {
      |                  ~~^~~~~~~~~~
wiring.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~

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