Submission #1042743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042743		aymanrs	Wiring (IOI17_wiring)	C++17	100 / 100	31 ms	11468 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<pair<int, bool>> ev;
	for(int i : r) ev.emplace_back(i, true);
	for(int i : b) ev.emplace_back(i, false);
	sort(ev.begin(), ev.end());
	long long p[ev.size()];
	for(int i = 0;i < ev.size();i++){
		p[i] = ev[i].first;
		if(i) p[i]+=p[i-1];
	}
	long long dp[ev.size()+1], sp[ev.size()+1];
	dp[0]=0;
	fill(dp+1, dp+ev.size()+1, LONG_LONG_MAX);
	long long S = 0;
	int c[ev.size()];
	int g = 0;
	for(int i = ev.size()-1;i >= 0;){
		int j = i;
		while(j >= 0 && ev[j].second == ev[i].second) {
			j--;
		}
		long long s = 0;
		for(int k = j+1;k <= i;k++){
			c[k] = min(j >= 0 ? ev[k].first-ev[j].first : INT_MAX,
			i+1 < ev.size() ? ev[i+1].first-ev[k].first : INT_MAX);
			S += c[k];
		}
		sp[i+1]=dp[0];
		for(int k = i;k > j;k--){
			sp[k]=sp[k+1];
			s += -ev[k].first-c[k];
			if(i-k+1 <= g && dp[i-k+1] < LONG_LONG_MAX) sp[k] = min(sp[k], dp[i-k+1]+s);
		}
		g = i-j;
		dp[0] = sp[j+1];
		s = 0;
		for(int k = 1;k <= g;k++){
			s += ev[j+k].first-c[j+k];
			dp[k] = s+sp[j+k+1];
		}
		i=j;
	}
	return S+dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0;i < ev.size();i++){
      |                ~~^~~~~~~~~~~
wiring.cpp:29:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    i+1 < ev.size() ? ev[i+1].first-ev[k].first : INT_MAX);
      |    ~~~~^~~~~~~~~~~

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