제출 #1074899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074899		LCJLY	Wiring (IOI17_wiring)	C++14	100 / 100	52 ms	14524 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
//#include "grader.cpp"
using namespace std;

#define int long long
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;

long long min_total_length(vector<int32_t>r, vector<int32_t>b) {
	int n=r.size();
	int m=b.size();
	vector<pii>v;
	for(int x=0;x<n;x++){
		v.push_back({r[x],0});
	}
	for(int x=0;x<m;x++){
		v.push_back({b[x],1});
	}
	sort(v.begin(),v.end());
	int dp[n+m+5];
	for(int x=0;x<=n+m;x++){
		dp[x]=1e17;
	}
	dp[0]=0;
	int prefix[n+m+5];
	memset(prefix,0,sizeof(prefix));
	for(int x=0;x<n+m;x++){
		prefix[x+1]=prefix[x]+v[x].first;
	}
	vector<vector<int>>blk;
	vector<int>cur={1};
	for(int x=1;x<n+m;x++){
		if(v[x].second!=v[x-1].second){
			blk.push_back(cur);
			cur.clear();
		}
		cur.push_back(x+1);
	}
	blk.push_back(cur);
	int sz=blk.size();
	for(int y=1;y<sz;y++){
		//y is more than y-1
		int ptr=(int)blk[y-1].size()-1;
		pii mini={1e17,-1};
		for(auto it:blk[y]){
			//show2(it,it,blk[y-1].back(),blk[y-1].back());
			mini=make_pair(mini.first-v[blk[y-1].back()-1].first+v[it-1].first,mini.second);
			if(ptr>=0){
				int index=blk[y-1][ptr];
				int cost=prefix[it]-prefix[blk[y][0]-1]-(prefix[blk[y-1].back()]-prefix[index-1])+min(dp[index-1],dp[index]);
				mini=min(mini,make_pair(cost,index));
				ptr--;
			}
			//show(mini.first,mini.first);
			dp[it]=min(dp[it],mini.first);
		}
		//show4(dp,dp);
		
		//y is less than y-1
		mini={1e17,-1};
		ptr=0;
		int diff=blk[y-1].size()-blk[y].size();
		for(int x=0;x<(int)blk[y-1].size()-(int)blk[y].size();x++){
			int index=blk[y-1][ptr];
			//show(index,index);
			//show2(a,a,b,b);
			int cost=prefix[blk[y].back()]-prefix[blk[y][0]-1]-(prefix[blk[y-1].back()]-prefix[index-1])+(diff-x)*v[blk[y][0]-1].first+min(dp[index-1],dp[index]);
			mini=min(mini,make_pair(cost,index));
			ptr++;
		}
		//show(mini.first,mini.first);
		diff=min(diff,0LL);
		for(int x=blk[y].size()-1+diff;x>=0;x--){
			int it=blk[y][x];
			mini=make_pair(mini.first-(x==(int)blk[y].size()-1?0:v[it].first-v[blk[y][0]-1].first),mini.second);
			//show(mini,mini.first);
			if(ptr<(int)blk[y-1].size()){
				int index=blk[y-1][ptr];
				//show(idnex,index);
				int cost=prefix[it]-prefix[blk[y][0]-1]-(prefix[blk[y-1].back()]-prefix[index-1])+min(dp[index-1],dp[index]);
				//show(cost,cost);
				mini=min(mini,make_pair(cost,index));
				ptr++;
			}
			//show2(it,it,mini.first,mini.first);
			dp[it]=min(dp[it],mini.first);
		}
		//show4(dp,dp);
	}
	return dp[n+m];
}

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