# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1036404 | beaconmc | Wiring (IOI17_wiring) | C++14 | 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>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll n,m;
vector<ll> R,B;
unordered_map<int,ll> cache;
unordered_map<int,ll> poses;
bool flag = true
ll dp(ll x, ll y){
if (flag && abs(poses[R[x]]-poses[B[y]]) > 20) return 1000000000000000;
if (cache.count(x*1000000+y)) return cache[x*1000000+y];
if (x==n && y==m) return 0;
if (x>=n || y >= m) return 1000000000000000;
return cache[x*1000000+y] = min(dp(x+1,y), min(dp(x,y+1), dp(x+1,y+1))) + abs(R[x] - B[y]);
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
flag = true;
R.clear();
B.clear();
vector<ll> stuff;
for (auto&i : r) stuff.push_back(i);
for (auto&i : b) stuff.push_back(i);
if (r.size() > 200 || b.size() > 200) flag = false;
sort(stuff.begin(), stuff.end());
FOR(i,0,stuff.size()){
poses[stuff[i]] = i;
}
cache.clear();
for (auto&i : r) R.push_back(i);
for (auto&i : b) B.push_back(i);
n = r.size();
m = b.size();
return dp(0,0);
}