Submission #827248

#TimeUsernameProblemLanguageResultExecution timeMemory
827248tranxuanbachWiring (IOI17_wiring)C++17
55 / 100
1000 ms237108 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(line_type l){ l.a = -l.a; l.b = -l.b; auto z = mts.insert(mts.end(), 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){ if (mts.empty()){ return infll; } auto l = *mts.lower_bound(x); return -(l.a * x + l.b); } }; int n, m; int a[N]; bool col[N]; pair <int, int> pre[N][2]; ll pref[N]; ll dp[N]; line_container seg[1 << 19]; void update(int id, int l, int r, int i, const line_container::line_type& ln){ seg[id].insert(ln); if (l == r){ return; } int mid = (l + r) >> 1; if (i <= mid){ update(id * 2, l, mid, i, ln); } else{ update(id * 2 + 1, mid + 1, r, i, ln); } } ll query(int id, int l, int r, int u, int v, ll x){ if (v < l or r < u){ return infll; } if (u <= l and r <= v){ return seg[id].query(x); } int mid = (l + r) >> 1; return min(query(id * 2, l, mid, u, v, x), query(id * 2 + 1, mid + 1, r, u, v, x)); } void update_dp(int i){ update(1, 0, n + m, i, line_container::line_type{i, dp[i] + pref[i]}); } ll min_total_length(vector <int> r, vector <int> b){ n = isz(r); m = isz(b); { int i = 0, j = 0; while (i < n or j < m){ if (j == m){ a[i + j + 1] = r[i]; col[i + j + 1] = true; i++; } else if (i == n){ a[i + j + 1] = b[j]; col[i + j + 1] = false; j++; } else if (r[i] < b[j]){ a[i + j + 1] = r[i]; col[i + j + 1] = true; i++; } else{ a[i + j + 1] = b[j]; col[i + j + 1] = false; j++; } } } 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; } pref[0] = 0; ForE(i, 1, n + m){ pref[i] = pref[i - 1] + a[i]; } fill(dp, dp + n + m + 1, infll); dp[0] = 0; update_dp(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], a[i] - a[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] - pref[j]) - (pref[j] - pref[j - leni]); int r = j - leni, l = k; // cout << l << ' ' << r << ' ' << query(1, 0, n + m, l, r, -(j + 1)) << endl; dp[i] = min(dp[i], sum + (ll)r * a[j + 1] - pref[r] + query(1, 0, n + m, l, r, -a[j + 1])); // for (int x = j - leni; x >= k; x--){ // dp[i] = min(dp[i], sum + dp[x]); // sum += (j + 1) - x; // } } // cout << "dp " << i << ' ' << dp[i] << endl; update_dp(i); } 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...