제출 #428348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428348		vanic	전선 연결 (IOI17_wiring)	C++14	0 / 100	1 ms	332 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];
vector < int > opcije;
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 pos;
	int visak;
	int pivot;
	for(int i=1; i<n+m; i++){
		if(svi[i].second!=svi[i-1].second){
			pivot=svi[i].first;
			pos=i-1;
			opcije.clear();
			while(pos>-1 && svi[pos].second==svi[i-1].second){
				opcije.push_back(pos);
				pos--;
			}
//			cout << opcije.size() << endl;
			reverse(opcije.begin(), opcije.end());
			visak=0;
			while(opcije.size()>1 && dp[opcije.back()]+(ll)(visak+1)*svi[i].first-(pref[i]-pref[opcije.back()])>dp[opcije[opcije.size()-2]]+(ll)(visak+2)*svi[i].first-(pref[i]-pref[opcije[opcije.size()-2]])){
				visak++;
				opcije.pop_back();
			}
//			cout << dp[opcije.back()] << ' ' << (visak+1)*svi[i].first-(pref[i]-pref[opcije.back()]) << endl;
			dp[i+1]=dp[opcije.back()]+(ll)(visak+1)*svi[i].first-(pref[i]-pref[opcije.back()]);
		}
		else{
			if(dp[i]==inf){
				dp[i+1]=inf;
				continue;
			}
			if(visak){
				dp[i+1]=dp[i]+svi[i].first-pivot;
				visak--;
			}
			else{
				if(opcije.size()>1 && dp[opcije.back()]>dp[opcije[opcije.size()-2]]+dist(opcije[opcije.size()-2], zadnji[svi[i].second^1])){
//					cout << "usaoo" << endl;
					dp[i+1]=dp[i]-dp[opcije.back()]+dp[opcije[opcije.size()-2]]+dist(opcije[opcije.size()-2], zadnji[svi[i].second^1]);
					opcije.pop_back();
				}
				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];
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:69:32: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     dp[i+1]=dp[i]+svi[i].first-pivot;
      |                                ^~~~~
wiring.cpp:70:10: warning: 'visak' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     visak--;
      |     ~~~~~^~

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