Submission #1060977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060977		vjudge1	Wiring (IOI17_wiring)	C++17	17 / 100	1084 ms	9164 KiB

wiring

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define c second
#define pt first
int const N=2e5+5;
ll const inf=1e16;
ll dp[N];
ll n,m;
vector<pair<ll,bool>> al;
ll min_total_length(vector<int> r, vector<int> b){
	n=r.size();
	m=b.size();
	al.push_back({-1,0});
	for(int i:r)
		al.push_back({i,0});
	for(int i:b)
		al.push_back({i,1});
	sort(al.begin(), al.end());
	for(int i=1;i<=n+m;i++)
		dp[i]=inf;
	for(int i=1;i<=n+m;i++){
		ll x=al[i].pt,y=0;
		ll min_x=al[i].pt,max_y=0;
		ll cx=1,cy=0;
		for(int j=i-1;j>=1;j--){
			if(al[j].c==al[i].c && al[j+1].c!=al[i].c)
				break;
			if(al[i].c==al[j].c){
				x+=al[j].pt;
				min_x=al[j].pt;
				cx++;
				continue;
			}
			y+=al[j].pt;
			max_y=max(max_y,al[j].pt);
			cy++;
			ll v=(x-(max_y*cx))+(cy*max_y)-y;
			v+=max(0LL,(cy-cx))*(min_x-max_y);
			ll mn=min(dp[j-1],dp[j])+v;
			dp[i]=min(dp[i],mn);
		}
	}
	return dp[n+m];
}

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