Submission #585201

#	Time	Username	Problem	Language	Result	Execution time	Memory
585201		Vanilla	Wiring (IOI17_wiring)	C++17	30 / 100	96 ms	16988 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
// int64 dp [maxn]; // dp[i] -> costul minim pentru a conecta primele i obiecte

int64 min_total_length(vector<int> r, vector<int> b) {
	int n = r.size();
	int m = b.size();
	vector <pair <int, int> > el;
	for (int i: r) {
		el.push_back({i, 0});
	}
	for (int i: b) {
		el.push_back({i, 1});
	}
	sort(el.begin(), el.end());
	vector <vector <int64> > block;
	vector <vector <int64> > pref;
	vector <vector <int64> > dp;
	for (int i = 0; i < el.size(); i++){
		if (i == 0 || el[i].second != el[i-1].second) block.push_back(vector <int64> (1, 0));
		block.back().push_back(el[i].first);
	}
	for (int i = 0; i < block.size(); i++){
		pref.push_back(vector <int64> (1, 0));
		dp.push_back(vector <int64> (block[i].size(), 1e15));
		for (int j = 1; j < block[i].size(); j++){
			pref[i].push_back(pref[i].back() + block[i][j]);
		}
	}
	dp[0][0] = 0;
	if (block.size() == 2) {
		for (int64 i = 1; i < block.size(); i++){
			dp[i][0] = dp[i-1].back();
			int64 j = block[i].size() - 1;
			int64 k = 1;
			int64 el2 = block[i-1].size() - k;
			if (j == el2) dp[i][j] = min(dp[i][j], dp[i-1][k-1] + pref[i][j] - (pref[i-1].back() - pref[i-1][k - 1])); // 0 0 1 1
			else if (j > el2) dp[i][j] = min(dp[i][j], dp[i-1][k-1] + pref[i][j] - (pref[i-1].back() - pref[i-1][k - 1] + (j - el2) * block[i-1].back())); // 0 0 1 1 1
			else if (j < el2) dp[i][j] = min(dp[i][j], dp[i-1][k-1] + pref[i][j] + (el2 - j) * block[i][1] - (pref[i-1].back() - pref[i-1][k - 1])); // 0 0 0 1 1
		}
		return dp.back().back();
	}
	for (int64 i = 1; i < block.size(); i++){
		dp[i][0] = dp[i-1].back();
		for (int64 j = 1; j < block[i].size(); j++){
			for (int64 k = block[i-1].size() - 1; k >= max((int64) (block[i-1].size() - 100), (int64) 1); k--){
				if (k == block[i-1].size() - 100) k = 1;
				int64 el2 = block[i-1].size() - k;
				if (j == el2) dp[i][j] = min(dp[i][j], min(dp[i-1][k], dp[i-1][k-1]) + pref[i][j] - (pref[i-1].back() - pref[i-1][k - 1])); // 0 0 1 1
				else if (j > el2) dp[i][j] = min(dp[i][j], min(dp[i-1][k], dp[i-1][k-1]) + pref[i][j] - (pref[i-1].back() - pref[i-1][k - 1] + (j - el2) * block[i-1].back())); // 0 0 1 1 1
				else if (j < el2) dp[i][j] = min(dp[i][j], min(dp[i-1][k], dp[i-1][k-1]) + pref[i][j] + (el2 - j) * block[i][1] - (pref[i-1].back() - pref[i-1][k - 1])); // 0 0 0 1 1
			}
		}
	}
	return dp.back().back();
}

Compilation message (stderr)

wiring.cpp: In function 'int64 min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < el.size(); i++){
      |                  ~~^~~~~~~~~~~
wiring.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < block.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
wiring.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int j = 1; j < block[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~
wiring.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int64' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int64 i = 1; i < block.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
wiring.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int64' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int64 i = 1; i < block.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
wiring.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int64 j = 1; j < block[i].size(); j++){
      |                     ~~^~~~~~~~~~~~~~~~~
wiring.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if (k == block[i-1].size() - 100) k = 1;
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:9:6: warning: unused variable 'n' [-Wunused-variable]
    9 |  int n = r.size();
      |      ^
wiring.cpp:10:6: warning: unused variable 'm' [-Wunused-variable]
   10 |  int m = b.size();
      |      ^

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