제출 #520297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520297		new_acc	Wiring (IOI17_wiring)	C++14	100 / 100	54 ms	11568 KiB

wiring

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second 
using namespace std;
const int N=5e5+10;
ll dp[N];
int n;
ll t[N*3];
ll sp[N*3];
ll sum(int a,int b,int p,int k){
	int mini=min(b-a+1,k-p+1);
	return (sp[a+mini-1]-sp[a-1])-(sp[k]-sp[k-mini])+(b-a>k-p?sp[b]-sp[a+mini-1]-(t[k]*(ll)(b-a+1-mini)):t[a]*(ll)(k-p+1-mini)-(sp[k-mini]-sp[p-1]));
}
void divide(int a,int b,int l,int r,int p1,int p2){
	if(b<a) return;
	int sr=(a+b)/2;
	int g=0;
	ll res=LLONG_MAX;
	for(int i=r;i>=l;i--){
		ll s=sum(p1,sr,i,p2)+dp[i-1];
		if(s<res) res=s,g=i;
	}
	dp[sr]=min(dp[p2]+sum(p1,sr,p2,p2),res); 
	divide(a,sr-1,g,r,p1,p2),divide(sr+1,b,l,g,p1,p2);
}
ll min_total_length(vector<int>r,vector<int>b){
	vector<pair<int,bool> >v;
	for(auto u:r) v.push_back({u,1});
	for(auto u:b) v.push_back({u,0});
	sort(v.begin(),v.end());
	int wsk=0;
	for(int i=0;i<(int)v.size();i++){
		int a=v[i].se;
		t[++wsk]=-1;
		while(i<(int)v.size()&&v[i].se==a) t[++wsk]=v[i].fi,i++;
		i--;
	}
	for(int i=1;i<=wsk;i++) sp[i]=sp[i-1]+(ll)t[i];	
	pair<int,int>l={0,0};
	for(int i=2;i<=wsk;i++){
		int j=i;
		while(i<=wsk&&t[i]!=-1) i++;
		i--;
		if(l.fi==0) for(int k=j;k<=i;k++) dp[k]=(ll)1e16;
		else{
			divide(j,i,l.fi,l.se,j,l.se);
			dp[j-1]=dp[l.se];
		}
		l={j,i};
		i++;
	}
	return dp[wsk];
}

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