Submission #1313059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313059		boclobanchat	Wiring (IOI17_wiring)	C++20	100 / 100	37 ms	8204 KiB

wiring

#include"wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long INF=1e18;
long long dp[MAXN],pref[MAXN];
bool comp(pair<long long,long long> a,pair<long long,long long> b)
{
	return a.second<b.second;
}
long long min_total_length(vector<int> A,vector<int> B)
{
	vector< pair<long long,long long> > vi;
	for(auto v:A) vi.push_back({0,v});
	for(auto v:B) vi.push_back({1,v});
	sort(vi.begin(),vi.end(),comp);
	int n=vi.size();
	for(int i=1;i<=n;i++) pref[i]=pref[i-1]+vi[i-1].second,dp[i]=INF;
	int pre=1;
	for(int i=1;i<n;i++) if(vi[i-1].first!=vi[i].first)
	{
		int pos=i+1;
		while(pos<=n&&vi[pos-1].first==vi[i].first) pos++;
		pos--;
		int p=pre,cnt=0;
		long long va=INF;
		for(int j=pos;j>i;j--)
		{
			int res=i-(j-i)+1;
			while(p<=res) va=min(va,min(dp[p-1],dp[p])+pref[p-1]-pref[i]*2+vi[i].second*(i-p+1)),p++;
			dp[j]=min(dp[j],va+pref[j]-vi[i].second*(j-i));
		}
		va=INF;
		for(int j=i+1;j<=pos;j++)
		{
			int pp=i-(j-i-1);
			va-=vi[i-1].second;
			if(pp>=pre) va=min(va,min(dp[pp],dp[pp-1])+pref[pp-1]-pref[i]*2);
			dp[j]=min(dp[j],va+pref[j]);
		}
		pre=i+1;
	}
	return dp[n];
}

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