Submission #428369

#	Time	Username	Problem	Language	Result	Execution time	Memory
428369		vanic	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	204 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]+(ll)(visak+1)*svi[i].first-(pref[i]-pref[d])>dp[d-1]+(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]=dp[d]+(ll)(visak+1)*svi[i].first-(pref[i]-pref[d]);
		}
		else{
			if(dp[i]==inf){
				dp[i+1]=inf;
				continue;
			}
			if(visak){
				dp[i+1]=dp[i]+svi[i].first-pivot;
				visak--;
			}
			else{
				if(d-1>l && dp[d]>dp[d-1]+dist(d-1, zadnji[svi[i].second^1])){
//					cout << "usaoo" << endl;
					dp[i+1]=dp[i]-dp[d]+dp[d-1]+dist(d-1, zadnji[svi[i].second^1]);
					d--;
				}
				else{
					dp[i+1]=dp[i];
				}
				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:70:21: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     if(d-1>l && dp[d]>dp[d-1]+dist(d-1, zadnji[svi[i].second^1])){
      |                 ~~~~^
wiring.cpp:70:14: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     if(d-1>l && dp[d]>dp[d-1]+dist(d-1, zadnji[svi[i].second^1])){
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:66:32: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     dp[i+1]=dp[i]+svi[i].first-pivot;
      |                                ^~~~~
wiring.cpp:67:10: warning: 'visak' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     visak--;
      |     ~~~~~^~

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