Submission #346742

#	Time	Username	Problem	Language	Result	Execution time	Memory
346742		wwdd	Wiring (IOI17_wiring)	C++14	100 / 100	104 ms	15700 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
const ll INFL = 1e18;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pl> wo;
	for(int i=0;i<r.size();i++) {
		wo.emplace_back(r[i],0);
	}
	for(int i=0;i<b.size();i++) {
		wo.emplace_back(b[i],1);
	}
	sort(wo.begin(),wo.end());
	vector<vl> sad,pad;
	int stt = -1;
	ll tot = 0;
	for(int i=0;i<wo.size();i++) {
		if(wo[i].second != stt) {
			stt = wo[i].second;
			sad.emplace_back();
			pad.emplace_back();
		}
		pad.back().push_back(wo[i].first);
	}
	for(int i=0;i<pad.size();i++) {
		for(int j=0;j<pad[i].size();j++) {
			ll x = pad[i][j];
			ll ma = INFL;
			if(i > 0) {
				ma = min(ma,x-pad[i-1].back());
			}
			if(i < pad.size()-1) {
				ma = min(ma,pad[i+1].front()-x);
			}
			sad[i].push_back(ma);
			tot += ma;
		}
	}
	vl dp(sad[0].size()+1,0);
	for(int i=1;i<sad.size();i++) {
		vl nx(sad[i].size()+1,0);
		ll sz = min(sad[i].size(),sad[i-1].size());
		vl tr;
		ll ma = 0;
		tr.push_back(0);
		ll trp = 0;
		for(int i=0;i<dp.size();i++) {
			trp = max(trp,dp[i]);
			dp[i] = trp;
		}
		for(int j=0;j<sz;j++) {
			tr.push_back(tr.back()
					-pad[i][j]+pad[i-1][pad[i-1].size()-j-1]
					+sad[i][j]+sad[i-1][sad[i-1].size()-j-1]);
		}
		for(int i=0;i<tr.size();i++) {
			nx[i] = dp[dp.size()-i-1] + tr[i];
		}
		dp = nx;
	}
	ll so = 0;
	for(int i=0;i<dp.size();i++) {
		so = max(so,dp[i]);
	}
	return tot-so;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<r.size();i++) {
      |              ~^~~~~~~~~
wiring.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<b.size();i++) {
      |              ~^~~~~~~~~
wiring.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<wo.size();i++) {
      |              ~^~~~~~~~~~
wiring.cpp:29:15: 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]
   29 |  for(int i=0;i<pad.size();i++) {
      |              ~^~~~~~~~~~~
wiring.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j=0;j<pad[i].size();j++) {
      |               ~^~~~~~~~~~~~~~
wiring.cpp:36:9: 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]
   36 |    if(i < pad.size()-1) {
      |       ~~^~~~~~~~~~~~~~
wiring.cpp:44:15: 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]
   44 |  for(int i=1;i<sad.size();i++) {
      |              ~^~~~~~~~~~~
wiring.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0;i<dp.size();i++) {
      |               ~^~~~~~~~~~
wiring.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i=0;i<tr.size();i++) {
      |               ~^~~~~~~~~~
wiring.cpp:48:6: warning: unused variable 'ma' [-Wunused-variable]
   48 |   ll ma = 0;
      |      ^~
wiring.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i=0;i<dp.size();i++) {
      |              ~^~~~~~~~~~

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