제출 #264180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264180		kshitij_sodani	Wiring (IOI17_wiring)	C++14	7 / 100	135 ms	28652 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;
		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);
		}
		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];

		/*queue<int> aa;
		queue<int> bb;
		vector<pair<int,int>> cc;
		for(auto j:r){
			cc.pb({j,0});
		}
		for(auto j:b){
			cc.pb({j,1});
		}
		sort(cc.begin(),cc.end());
		for(auto j:cc){
			
			if(j.b==0){
				if(bb.size()==0){
					aa.push(j.a);
					continue;
				}
				int x=bb.front();
				bb.pop();
				ans+=j.a-x;
			}
			else{
				if(aa.size()==0){
					bb.push(j.a);
					continue;
				}
				int x=aa.front();
				aa.pop();
				ans+=j.a-x;
			}			
		}*/


		
		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: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45