Submission #264283

#	Time	Username	Problem	Language	Result	Execution time	Memory
264283		kshitij_sodani	Wiring (IOI17_wiring)	C++14	13 / 100	144 ms	22756 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second



#include "wiring.h"
llo dp[201][201];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n,m;
	n=r.size();
	m=b.size();

	llo ans=0;
	vector<llo> co;
	vector<llo> co2;
	set<int> mi;
	set<int> ma;
	//find min points
	for(auto j:r){
		mi.insert(j);
	}
	for(auto j:b){
		ma.insert(j);
	}
	for(auto x:r){
		auto j=ma.lower_bound(x);
		int cur=1e9;
		if(j!=ma.end()){
			cur=min(cur,abs((*j)-x));
		}
		if(j!=ma.begin()){
			j--;
			cur=min(cur,abs((*j)-x));
		}
		ans+=cur;
		co.pb(cur);
	}
	for(auto x:b){
		auto j=mi.lower_bound(x);
		int cur=1e9;
		if(j!=mi.end()){
			cur=min(cur,abs((*j)-x));
		}
		if(j!=mi.begin()){
			j--;
			cur=min(cur,abs((*j)-x));
		}
		ans+=cur;
		co2.pb(cur);
	}
	//end min points 
		multiset<llo> aa;
		multiset<llo> bb;
		vector<pair<llo,llo>> cc;
		llo ii=0;
		for(auto j:r){
			cc.pb({j,ii});
			ii++;
		}
		for(auto j:b){
			cc.pb({j,ii});
			ii++;
		}
		sort(cc.begin(),cc.end());
		for(auto j:cc){
			
			if(j.b<n){
				if(bb.size()==0){
					aa.insert(-j.a-co[j.b]);
					continue;
				}
				int x=*bb.begin();
				if(j.a+x-co[j.b]>0){
					aa.insert(-j.a-co[j.b]);
					continue;
				}
				bb.erase(bb.begin());
				ans+=j.a+x-co[j.b];
			}
			else{
				if(aa.size()==0){
					bb.insert(-j.a-co2[j.b-n]);
					continue;
				}
				int x=*aa.begin();
				if(j.a+x-co2[j.b-n]>0){
					bb.insert(-j.a-co2[j.b-n]);
					continue;
				}
				aa.erase(aa.begin());
				ans+=j.a+x-co2[j.b-n];
			}			
		}
		return ans;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dp[i][j]=abs(r[i-1]-b[j-1])-co[i-1]-co2[j-1]+dp[i-1][j-1];
				dp[i][j]=min(dp[i][j],min(dp[i-1][j],dp[i][j-1]));
			}
		}
		return ans+dp[n][m];

		


		
		return ans;
	/*}
*/



	/*vector<int> rr;
	vector<int> bb;
	while(r.size() or b.size()){
		for(auto i:r){
			for(auto j:b){



			}
		}
	}


*/








	return ans;
}




/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	return 0;
}
*/

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