Submission #1313041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313041		boclobanchat	Wiring (IOI17_wiring)	C++20	7 / 100	97 ms	6156 KiB

wiring

#include"wiring.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=444;
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);
	for(int i=1;i<=vi.size();i++)
	{
		dp[i]=INF,pref[i]=pref[i-1]+vi[i-1].second;
		int chain=0,pos=0;
		for(int j=i-1;j;j--)
		{
			if(vi[j-1].first!=vi[j].first) chain++,pos=j+1;
			if(chain==2) break;
			if(chain)
			{
				long long a=i-pos+1,b=pos-j;
				long long res=(pref[i]-pref[pos-1])-(pref[pos-1]-pref[j-1])+vi[pos-1].second*(b-min(a,b))-vi[pos-2].second*(a-min(a,b));
				dp[i]=min(dp[i],dp[j-1]+res);
				dp[i]=min(dp[i],dp[j]+res);
			}
		}
	}
	return dp[vi.size()];
}

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