제출 #827165

#제출 시각아이디문제언어결과실행 시간메모리
827165tranxuanbach전선 연결 (IOI17_wiring)C++17
0 / 100
1083 ms11148 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define For(i, l, r) for (auto i = (l); i < (r); i++) #define ForE(i, l, r) for (auto i = (l); i <= (r); i++) #define FordE(i, l, r) for (auto i = (l); i >= (r); i--) #define bend(a) (a).begin(), (a).end() #define isz(a) ((ll)(a).size()) using ll = long long; const ll infll = (ll)1e18 + 7; const int N = 2e5 + 5; struct line_container{ struct line_type{ ll a, b; mutable ll p; bool operator< (const line_type& oth) const{ return a < oth.a; } bool operator< (ll x) const{ return p < x; } }; multiset <line_type, less<>> mts; const ll inf = infll; ll div(ll x, ll y){ return x / y - ((x ^ y) < 0 and x % y); } template <class T> bool isect(T x, T y){ if (y == mts.end()){ x->p = infll; return false; } if (x->a == y->a){ x->p = x->b > y->b ? infll : -infll; } else{ x->p = div(y->b - x->b, x->a - y->a); } return x->p >= y->p; } void insert(const line_type& l){ auto z = mts.insert(l), y = z++, x = y; while (isect(y, z)){ z = mts.erase(z); } if (x != mts.begin() and isect(--x, y)){ isect(x, mts.erase(y)); } while ((y = x) != mts.begin() and (--x)->p >= y->p){ isect(x, mts.erase(y)); } } ll query(ll x){ auto l = *mts.lower_bound(x); return l.a * x + l.b; } }; int n, m; bool col[N]; pair <int, int> pre[N][2]; ll pref[N][2]; ll dp[N]; ll min_total_length(vector <int> r, vector <int> b){ n = isz(r); m = isz(b); for (auto pos: r){ col[pos] = true; } for (auto pos: b){ col[pos] = false; } pre[0][0] = pair{0, 0}; pre[0][1] = pair{0, 0}; ForE(i, 1, n + m){ pre[i][0] = pre[i - 1][0]; pre[i][1] = pre[i - 1][1]; swap(pre[i][col[i]].fi, pre[i][col[i]].se); pre[i][col[i]].fi = i; // cout << i << ' ' << pre[i][0].fi << ' ' << pre[i][0].se << ' ' << pre[i][1].fi << ' ' << pre[i][1].se << endl; } pref[0][0] = 0; pref[0][1] = 0; ForE(i, 1, n + m){ pref[i][0] = pref[i - 1][0] + (col[i] == 0 ? i : 0); pref[i][1] = pref[i - 1][1] + (col[i] == 1 ? i : 0); } fill(dp, dp + n + m + 1, infll); dp[0] = 0; ForE(i, 1, n + m){ if (pre[i][0].fi == 0 or pre[i][1].fi == 0){ continue; } int j = pre[i][col[i] ^ 1].fi; dp[i] = min(dp[i], i - j + dp[i - 1]); int k = pre[j][col[i]].fi; int leni = i - j, lenj = j - k; if (leni <= lenj){ ll sum = (pref[i][col[i]] - pref[j][col[i]]) - (pref[j][col[i] ^ 1] - pref[j - leni][col[i] ^ 1]); for (int l = j - leni; l >= k; l--){ dp[i] = min(dp[i], sum + dp[l]); sum += (j + 1) - l; } } // cout << i << ' ' << dp[i] << endl; } return dp[n + m]; }
#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...