Submission #428499

#	Time	Username	Problem	Language	Result	Execution time	Memory
428499		vanic	Wiring (IOI17_wiring)	C++14	100 / 100	68 ms	8496 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;
const ll inf=1e16;

int n, m;
pair < int, bool > svi[maxn];
ll pref[maxn];
ll dp[maxn];

inline ll dist(int ind1, int ind2){
	return abs(svi[ind1].first-svi[ind2].first);
}

ll min_total_length(vector < int > r, vector < int > b){
	n=r.size();
	m=b.size();
	for(int i=0; i<n; i++){
		svi[i]={r[i], 0};
	}
	for(int i=0; i<m; i++){
		svi[i+n]={b[i], 1};
	}
	sort(svi, svi+n+m);
	for(int i=0; i<n+m; i++){
		pref[i+1]=pref[i]+svi[i].first;
	}
	int zadnji[]={-1, -1};
	zadnji[svi[0].second]=svi[0].first;
	dp[1]=inf;
	int visak;
	int pivot;
	int l, d;
	for(int i=1; i<n+m; i++){
		if(svi[i].second!=svi[i-1].second){
			pivot=svi[i].first;
			l=i-1;
			d=i-1;
			while(l>-1 && svi[l].second==svi[i-1].second){
				l--;
			}
//			cout << opcije.size() << endl;
			visak=0;
			while(d-1>l && (dp[d]==inf || min(dp[d], dp[d+1])+(ll)(visak+1)*svi[i].first-(pref[i]-pref[d])>min(dp[d-1], dp[d])+(ll)(visak+2)*svi[i].first-(pref[i]-pref[d-1]))){
				visak++;
				d--;
			}
//			cout << dp[opcije.back()] << ' ' << (visak+1)*svi[i].first-(pref[i]-pref[opcije.back()]) << endl;
			dp[i+1]=min(dp[d], dp[d+1])+(ll)(visak+1)*svi[i].first-(pref[i]-pref[d]);
		}
		else{
			if(dp[i]==inf){
				dp[i+1]=inf;
				zadnji[svi[i].second]=svi[i].first;
				continue;
			}
			if(visak){
//				cout << "unutra " << endl;;
				dp[i+1]=dp[i]+svi[i].first-pivot;
				visak--;
			}
			else{
				if(d-1>l && dp[d]>dp[d-1]+zadnji[svi[i].second^1]-svi[d-1].first){
//					cout << "usaoo" << endl;
					dp[i+1]=dp[i]-dp[d]+dp[d-1]+zadnji[svi[i].second^1]-svi[d-1].first;
					d--;
				}
				else{
					dp[i+1]=dp[i];
				}
//				cout << svi[i].first-zadnji[svi[i].second^1] << endl;
				dp[i+1]+=svi[i].first-zadnji[svi[i].second^1];
			}
		}
		zadnji[svi[i].second]=svi[i].first;
	}
/*	for(int i=0; i<=n+m; i++){
		cout << dp[i] << ' ';
	}
	cout << endl;*/
	return dp[n+m];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:72:21: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     if(d-1>l && dp[d]>dp[d-1]+zadnji[svi[i].second^1]-svi[d-1].first){
      |                 ~~~~^
wiring.cpp:72:5: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     if(d-1>l && dp[d]>dp[d-1]+zadnji[svi[i].second^1]-svi[d-1].first){
      |     ^~
wiring.cpp:68:32: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |     dp[i+1]=dp[i]+svi[i].first-pivot;
      |                                ^~~~~
wiring.cpp:69:10: warning: 'visak' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     visak--;
      |     ~~~~~^~

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