Submission #56269

#	Time	Username	Problem	Language	Result	Execution time	Memory
56269		Kerim	전선 연결 (IOI17_wiring)	C++17	100 / 100	103 ms	7916 KiB

wiring

#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll dp[MAXN],par[MAXN];
ll min_total_length(vector<int>a,vector<int>b){
	int n=a.size();
	int m=b.size();
	vector<PII>v;
	for(int i=0;i<n;i++)
		v.pb(mp(a[i],0));
	for(int i=0;i<m;i++)
		v.pb(mp(b[i],1));
	v.pb(mp(-1,-1));	
	sort(all(v));
	vector<PII>len;
	for(int i=1;i<int(v.size());i++)
		par[i]=par[i-1]+v[i].ff;
	for(int i=1;i<int(v.size());i++){
		int j=i;
		while(j<int(v.size()) and v[i].ss==v[j].ss)
			j++;
		len.pb(mp(i,j-1));	
		i=j-1;	
	}	
	if(len.size()==1)
		return 0;
	for(int i=len[0].ff;i<=len[0].ss;i++)
		dp[i]=dp[i-1]+v[len[1].ff].ff-v[i].ff;
	for(int i=1;i<min(INF,int(len.size()));i++){
		int a=len[i-1].ff,b=len[i-1].ss;
		int c=len[i].ff,d=len[i].ss;
		int sz=min(b-a,d-c)+1;
		for(int j=1;j<=sz;j++){
			if(b-a+1>j)
				dp[c+j-1]=(par[c+j-1]-par[c-1])-(par[b]-par[b-j])+dp[b-j];
			else{
				if(i>1)
					dp[c+j-1]=(par[c+j-1]-par[c-1])-(par[b]-par[b-j])+dp[len[i-2].ss];
				else
					dp[c+j-1]=(par[c+j-1]-par[c-1])-(par[b]-par[b-j]);	
			}
			if(j>1){
				umin(dp[c+j-1],dp[c+j-2]+v[c+j-1].ff-v[b].ff);
				if(i+1<int(len.size()))
					umin(dp[c+j-1],dp[c+j-2]+v[len[i+1].ff].ff-v[c+j-1].ff);
			}
			else{
				umin(dp[c],1LL*v[c].ff-v[b].ff+dp[b]);
				if(i+1<int(len.size()))
					umin(dp[c],1LL*v[len[i+1].ff].ff-v[c].ff+dp[b]);
			}
			//~ cout<<dp[c+j-1]<<" "<<c+j-1<<endl;
		}
		for(int j=sz+1;j<=d-c+1;j++){
			dp[c+j-1]=dp[c+j-2]+v[c+j-1].ff-v[b].ff;
			if(i+1<int(len.size()))
				umin(dp[c+j-1],dp[c+j-2]+v[len[i+1].ff].ff-v[c+j-1].ff);
			//~ cout<<dp[c+j-1]<<" "<<c+j-1<<endl;	
		}
	}	
	return dp[v.size()-1];	
}
//I want O(N) solution :)
//succed ? yes or no
//~ int main(){
    //~ freopen("file.in", "r", stdin);
    //~ int n,m;
    //~ cin>>n;
    //~ vector<int>a,b;
    //~ while(n--){
		//~ int x;
		//~ scanf("%d",&x);a.pb(x);
	//~ }
	//~ cin>>m;
	//~ while(m--){
		//~ int x;
		//~ scanf("%d",&x);b.pb(x);
	//~ }
	//~ printf("%lld\n",min_total_length(a,b));
	//~ return 0;
//~ }
//~ 

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