Submission #587939

#	Time	Username	Problem	Language	Result	Execution time	Memory
587939		Soumya1	Wiring (IOI17_wiring)	C++17	100 / 100	65 ms	10900 KiB

wiring

#include "wiring.h"
// #include <debug_local.h>
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
long long min_total_length(vector<int> r, vector<int> b) {
	vector<pair<int, int>> a;
	for (int i : r) a.push_back({i, 1});
	for (int i : b) a.push_back({i, 2});
	sort(a.begin(), a.end());
	vector<vector<int>> v;
 	for (int i = 0; i < a.size(); i++) {
		int j = i;
		v.push_back({});
		while (j < a.size() && a[i].second == a[j].second) {
			v.back().push_back(a[j].first);
			j++;
		}
		i = j - 1;
	}
	vector<long long> suf(v[0].size() + 1, inf);
	auto pref = suf;

	suf[v[0].size()] = 0;
	for (int i : v[0]) suf[v[0].size()] -= i;
	suf[v[0].size()] += 1LL * v[0].size() * v[1][0];

	pref[v[0].size()] = 0;
	for (int i : v[0]) pref[v[0].size()] -= i;
	pref[v[0].size()] += 1LL * v[0].size() * v[0].back();

	for (int i = 1; i < pref.size(); i++) pref[i] = min(pref[i], pref[i - 1]);
	for (int i = suf.size() - 2; i >= 0; i--) suf[i] = min(suf[i], suf[i + 1]);

	vector<long long> final;
	for (int i = 1; i < v.size(); i++) {
		int s = v[i].size();
		vector<long long> dp(s + 1, inf);
		long long sum = 0;
		for (int take = 0; take <= v[i].size(); take++) {
			dp[take] = min(dp[take], (take < pref.size() ? pref[take] : pref.back()) + sum - 1LL * take * v[i - 1].back());
			dp[take] = min(dp[take], (take < suf.size() ? suf[take] : inf) + sum - 1LL * take * v[i][0]);
			if (take < v[i].size()) sum += v[i][take];
		}
		sum = 0;
		suf.assign(s + 1, inf);
		pref.assign(s + 1, inf);
		for (int take = v[i].size(); take >= 0; take--) { 
			int idx = v[i].size() - take;
			if (take < v[i].size()) sum += v[i][take];
			suf[idx] = pref[idx] = dp[take] - sum;
			if (i + 1 < v.size()) suf[idx] += 1LL * (v[i].size() - take) * v[i + 1][0];
			pref[idx] += 1LL * (v[i].size() - take) * v[i].back();
		}
		for (int j = 1; j < pref.size(); j++) pref[j] = min(pref[j], pref[j - 1]);
		for (int j = suf.size() - 2; j >= 0; j--) suf[j] = min(suf[j], suf[j + 1]);
		if (i + 1 == v.size()) {
			return dp.back();
		}
	}
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   for (int i = 0; i < a.size(); i++) {
      |                   ~~^~~~~~~~~~
wiring.cpp:15: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]
   15 |   while (j < a.size() && a[i].second == a[j].second) {
      |          ~~^~~~~~~~~~
wiring.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 1; i < pref.size(); i++) pref[i] = min(pref[i], pref[i - 1]);
      |                  ~~^~~~~~~~~~~~~
wiring.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
wiring.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int take = 0; take <= v[i].size(); take++) {
      |                      ~~~~~^~~~~~~~~~~~~~
wiring.cpp:41:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    dp[take] = min(dp[take], (take < pref.size() ? pref[take] : pref.back()) + sum - 1LL * take * v[i - 1].back());
      |                              ~~~~~^~~~~~~~~~~~~
wiring.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    dp[take] = min(dp[take], (take < suf.size() ? suf[take] : inf) + sum - 1LL * take * v[i][0]);
      |                              ~~~~~^~~~~~~~~~~~
wiring.cpp:43:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (take < v[i].size()) sum += v[i][take];
      |        ~~~~~^~~~~~~~~~~~~
wiring.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    if (take < v[i].size()) sum += v[i][take];
      |        ~~~~~^~~~~~~~~~~~~
wiring.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if (i + 1 < v.size()) suf[idx] += 1LL * (v[i].size() - take) * v[i + 1][0];
      |        ~~~~~~^~~~~~~~~~
wiring.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int j = 1; j < pref.size(); j++) pref[j] = min(pref[j], pref[j - 1]);
      |                   ~~^~~~~~~~~~~~~
wiring.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if (i + 1 == v.size()) {
      |       ~~~~~~^~~~~~~~~~~
wiring.cpp:7:25: warning: control reaches end of non-void function [-Wreturn-type]
    7 |  vector<pair<int, int>> a;
      |                         ^

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