| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1265310 | scalifrastico_098 | 전선 연결 (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector<long long> r, vector<int> b) {
long long inf=1e9+7;
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(long long i=0; i<n1; i++)
{
for(long long u=0; u<=n1; u++)
{
if(dp[i][u]>=INT_MAX) continue;
for(long long j=0; j<i; j++)
{
if(op[j].second.first==op[i].second.first) continue;
if(u!=n1&&j==u) continue;
long long co=abs(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=abs(op[u].first-op[i].first);
dp[i+1][n1]=min(dp[i+1][n1], dp[i][u]+co);
}
}
}
}
return dp[n1][n1];
}