Submission #1213456

#TimeUsernameProblemLanguageResultExecution timeMemory
1213456sanoWiring (IOI17_wiring)C++20
42 / 100
43 ms14760 KiB
#include "wiring.h" #include<iostream> #include<vector> #include<queue> #include<deque> #include<string> #include<fstream> #include<algorithm> #include <iomanip> #include<map> #include <set> #include <unordered_map> #include <stack> #include <unordered_set> #include <cmath> #include <random> #define ll long long #define For(i, n) for(ll i = 0; i < (ll)n; i++) #define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++) #define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--) #define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--) #define vec vector #define ff first #define ss second #define pb push_back #define shit short int #define pii pair<ll, ll> #define NEK 1000000000000 #define mod 1000000007 #define mod2 1000000009 #define rsz resize #define prv1 43 #define prv2 47 using namespace std; ll min_total_length(vec<int> r2, vec<int> b2) { vec<ll> r, b; vec<pii> p; For(i, r2.size()) r.push_back(r2[i]); For(i, b2.size()) b.push_back(b2[i]); ll pr = r.size(); ll p_b = b.size(); ll n = pr + p_b; For(i, pr) { p.push_back({ r[i], 0 }); } For(i, p_b) { p.push_back({ b[i], 1 }); } sort(p.begin(), p.end()); vec<ll> dp(n + 1, NEK); dp[0] = 0; vec<ll> bl(n, NEK); ll pos0 = -1, pos1 = -1; For(i, n) { if (p[i].ss == 0) { pos0 = p[i].ff; if (pos1 == -1) continue; bl[i] = min(bl[i], p[i].ff - pos1); } if (p[i].ss == 1) { pos1 = p[i].ff; if (pos0 == -1) continue; bl[i] = min(bl[i], p[i].ff - pos0); } } pos0 = -1, pos1 = -1; rfor(i, n-1) { if (p[i].ss == 0) { pos0 = p[i].ff; if (pos1 == -1) continue; bl[i] = min(bl[i], pos1 - p[i].ff); } if (p[i].ss == 1) { pos1 = p[i].ff; if (pos0 == -1) continue; bl[i] = min(bl[i], pos0 - p[i].ff); } } ll prvy = 0; ll posl = 0; ll pointer = -1; vec<ll> p_vzd(n, -1); ll trz_vzd = 0; priority_queue<pii> q; ll min_pred = NEK; ffor(i, 1, n + 1) { //jednoducho ho napoj na najblizsieho dp[i] = min(dp[i], dp[i - 1] + bl[i - 1]); if (p[i - 1].ss != p[prvy].ss) { while (!q.empty()) q.pop(); ll vzd = 0; for (ll j = i - 2; j >= prvy; j--) { vzd += p[i - 2].ff - p[j].ff; p_vzd[j] = vzd; q.push({ (dp[j] + vzd + (i - 1 - j) * (p[i - 1].ff - p[i - 2].ff)) * (-1), j}); } posl = prvy; pointer = i - 2; prvy = i - 1; trz_vzd = 0; min_pred = NEK; } trz_vzd += p[i-1].ff - p[prvy].ff; //vzd1 jedna co si budem predpocitavat //trz_vzd + vzd2 + dp[i-1] + MAX(POCA, POCB) * (dist) ll pocb = (i - prvy); while (pointer >= posl && (prvy - pointer) <= (i - prvy)) { min_pred = min(min_pred, p_vzd[pointer] + dp[pointer]); pointer--; } //musime vyhodit vsetkych mojov ktory uz zrazu niesu v ponuke while (!q.empty()) { if (q.top().ss > pointer) q.pop(); else break; } ll min_druhe = NEK; if (!q.empty()) { min_druhe = q.top().ff * (-1) + trz_vzd; } ll odp = NEK; if (prvy != 0) { odp = min_pred + trz_vzd + pocb * (p[prvy].ff - p[prvy - 1].ff); } dp[i] = min(dp[i], min(min_druhe, odp)); } return dp[n]; } /* signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vec<int> a(n), b(m); For(i, n) cin >> a[i]; For(i, m) cin >> b[i]; cout << min_total_length(a, b) << '\n'; 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...