제출 #1265314

#제출 시각아이디문제언어결과실행 시간메모리
1265314scalifrastico_098Wiring (IOI17_wiring)C++20
0 / 100
0 ms324 KiB
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<int> r, vector<int> b) {
	long long inf=4e18;
	long long n=r.size(), m=b.size(); int n1=n+m;vector<vector<long long>> dp(n1+1, vector<long long> (n1+1,inf)); dp[0][n1]=0; 
	vector<pair<long long, pair<char, long long>>> op; op.reserve(n1);
	for(auto x:r){op.push_back({x, {'R',0}});}
	for(auto x:b){op.push_back({x, {'B',0}});}
	sort(op.begin(), op.end());
	for(int i=0; i<n1; i++)
	{
		for(int u=0; u<=n1; u++)
		{
			if(dp[i][u]>=inf) continue;
			for(int j=0; j<i; j++)
			{
				if(op[j].second.first==op[i].second.first) continue;
				if(u!=n1&&j==u) continue;
				long long co=llabs(op[i].first-op[j].first); dp[i+1][u]=min(dp[i+1][u], co+dp[i][u]);
			}
			if(u==n1){dp[i+1][i]=min(dp[i+1][i], dp[i][u]);}
			else
			{
				if(op[u].second.first!=op[i].second.first)
				{
					long long co=llabs(op[u].first-op[i].first);
					dp[i+1][n1]=min(dp[i+1][n1], dp[i][u]+co);
				}
			}
		}
	}
	return dp[n1][n1]-1;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...