제출 #1265314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265314		scalifrastico_098	전선 연결 (IOI17_wiring)	C++20	0 / 100	0 ms	324 KiB

wiring

#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;
}

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