| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1107066 | Requiem | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "wiring.h"
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "wiring"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
/**
Ta cần phải:
- Ghép nối các thằng đó sao cho mỗi thằng đỏ luôn được nối với 1 thằng xanh và chi phí nối là nhỏ nhất.
- Chi phí ghép nối giữa thằng i và j là abs(p[i] - p[j]).
subtask 1: n <= 200, m <= 200
dp_i_j_k: xét đến vị trí i, còn j thằng đỏ chưa đc ghép cặp, còn k thằng xanh chưa đc ghép cặp.
dp_i_j_k --> dp_(i + 1)_(j - 1)_k (nếu j > 0 va thang i + 1 la xanh)
--> dp_(i + 1)_j_(k - 1) (neu k > 0 va thang i + 1 la đỏ)
--> dp_(i + 1)_(j + 1)_k
--> dp_(i + 1)_j_(k + 1)
--> dp_(i + 1)_0_k nếu ko còn thằng đối màu để ghép
**/
namespace subtask1{
bool check(vector<int> r, vector<int> b){
return r.size() <= 200 and b.size() <= 200;
}
int n,m ;
ll dp[201][201][201], lastRed = 0, lastBlue = 0;
struct point{
ll x;
ll color;
point(ll _x = 0, ll _color = 0): x(_x), color(_color) {}
bool operator < (const point &other) const {
return x < other.x;
}
};
vector<point> p;
ll solve(vector<int> r, vector<int> b){
n = r.size();
m = b.size();
FOR(i, 0, n - 1){
p.pb(point(r[i], 0));
}
FOR(i, 0, m - 1){
p.pb(point(b[i], 1));
}
sort(p.begin(), p.end());
memset(dp, 0x3f, sizeof(dp));
dp[0][0][0] = 0;
lastRed = -1, lastBlue = -1;
FOR(i, 0, (int) p.size() - 1){
// cout << p[i].x << ' ' << p[i].color << endl;
FOR(remainingRed, 0, n){
FOR(remainingBlue, 0, m){
if (dp[i][remainingRed][remainingBlue] < inf){
if (p[i].color == 0) { //bi do
if (remainingBlue > 0) minimize(dp[i + 1][remainingRed][remainingBlue - 1],
dp[i][remainingRed][remainingBlue] + p[i].x); //dong 1 bi do
if (remainingBlue == 0 and lastBlue != -1) minimize(dp[i + 1][remainingRed][remainingBlue],
dp[i][remainingRed][remainingBlue] + p[i].x - lastBlue); //ghep voi 1 thang da dc ghep
minimize(dp[i + 1][remainingRed + 1][remainingBlue], dp[i][remainingRed][remainingBlue] - p[i].x); //mo 1 thang bi do
}
else{
if (remainingRed > 0) minimize(dp[i + 1][remainingRed - 1][remainingBlue],
dp[i][remainingRed][remainingBlue] + p[i].x); //dong 1 bi do
if (remainingBlue == 0 and lastRed != -1) minimize(dp[i + 1][remainingRed][remainingBlue],
dp[i][remainingRed][remainingBlue] + p[i].x - lastRed); //ghep voi 1 thang da dc ghep
minimize(dp[i + 1][remainingRed][remainingBlue + 1], dp[i][remainingRed][remainingBlue] - p[i].x); //mo 1 thang bi do
}
}
}
}
if (p[i].color == 0) lastRed = p[i].x;
else lastBlue = p[i].x;
}
return dp[(int)p.size()][0][0];
}
}
ll min_total_length(vector<int> r, vector<int> b){
if (subtask1::check(r, b)) return subtask1::solve(r, b);
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
int n, m;
vector<int> r, b;
cin >> n >> m;
r.resize(n);
FOR(i, 0, n - 1){
cin >> r[i];
}
b.resize(m);
FOR(i, 0, m - 1){
cin >> b[i];
}
cout << min_total_length(r, b)<< endl;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/