제출 #389969

#제출 시각아이디문제언어결과실행 시간메모리
389969Keshi전선 연결 (IOI17_wiring)C++17
0 / 100
1091 ms6064 KiB
//In the name of God #include <bits/stdc++.h> #include "wiring.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 2e5 + 100; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) ll ls[maxn], dp[maxn]; vector<pll> a; ll solve(ll k, ll j, ll i){ ll x = 0; for(ll o = k; o < j; o++){ x += a[j + 1].F - a[o + 1].F; } for(ll o = j + 1; o <= i; o++){ x += a[o].F - a[j].F; } if(i - j > 1) x -= a[j + 1].F - a[j].F; if(j - k > 1) x -= a[j + 1].F - a[j].F; if(i - k == 2) x -= a[j + 1].F - a[j].F; return x + dp[k + 1]; } ll get(ll i){ ll j = ls[i]; if(j == -1) return inf; ll k = ls[j]; ll x = inf; for(ll o = k; o < j; o++){ x = min(x, solve(o, j, i)); } return x; } long long min_total_length(vector<int> r, vector<int> b){ for(ll i : r){ a.pb(Mp(i, 0)); } for(ll j : b){ a.pb(Mp(j, 1)); } sort(all(a)); ll las[2] = {-1, -1}; ll n = Sz(a); for(ll i = 0; i < n; i++){ ls[i] = las[a[i].S ^ 1]; las[a[i].S] = i; ll j = ls[i]; dp[i + 1] = get(i); continue; if(j == -1) continue; if(i - j > 2){ dp[i + 1] = dp[i] + a[i].F - a[j].F; continue; } if(i - j == 1){ ll x = 0; for(ll k = j; k > ls[j]; k--){ x += a[i].F - a[k].F; dp[i + 1] = min(dp[i + 1], dp[k] + x); } continue; } ll x = a[i].F - a[j].F; dp[i + 1] = x + a[i - 1].F - a[j].F + dp[j]; for(ll k = j - 1; k > ls[j]; k--){ x += a[i - 1].F - a[k].F; dp[i + 1] = min(dp[i + 1], dp[k] + x); } } return dp[n]; } /*int main(){ fast_io; return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...