| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077764 | TB_ | 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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define all(x) x.begin(), x.end()
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
vector<unordered_map<ll, ll>> memo;
ll n;
vpl v;
ll dp(ll pos, ll am, ll red = 1, ll changed = 0){
if(am>10) return 1e18;
if(pos == n) return (am?1e18:0);
if(memo[pos].count(red+changed*2+am*4)) return memo[pos][red+changed*2+am*4];
ll &ans = memo[pos][red+changed*2+am*4];
// deb2(pos, am);
ans = 1e18;
if(changed) ans = dp(pos+1, am, red)+(v[pos+1].F-v[pos].F)*am;
if(am==0) ans = min(dp(pos, am+1, v[pos].S, 1), ans);
else if(v[pos].S == red) ans = min(dp(pos, am+1, red, 1), ans);
else ans = min(dp(pos, am-1, red, 1), ans);
return ans;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
fo(i, r.size()){
v.pb({r[i], 1});
}
fo(i, b.size()){
v.pb({b[i], 0});
}
sort(all(v));
n = v.size();
v.pb(v[n-1]);
memo.assign(n+1, {});
return dp(0, 0);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
// vector<int> a = {0};
// vector<int> b = {2};
vector<int> a = {1, 2, 3, 7};
vector<int> b = {0, 4, 5, 9, 10};
deb(min_total_length(a, b));
return 0;
}