Submission #39468

#TimeUsernameProblemLanguageResultExecution timeMemory
39468qoo2p5Palembang Bridges (APIO15_bridge)C++14
0 / 100
0 ms2180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = (int) 1e9 + 123; const ll LINF = (ll) 1e18 + 123; #define rep(i, s, t) for (auto i = (s); i < (t); ++(i)) #define per(i, s, t) for (auto i = (s); i >= (t); --(i)) #define sz(x) ((int) (x).size()) #define mp make_pair #define pb push_back #define all(x) (x).begin(), (x).end() bool mini(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } bool maxi(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } void run(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); run(); return 0; } const int N = (int) 1e5 + 123; int k, n; vector<pair<ll, ll>> a; vector<ll> cool; ll total; void solve1() { int ptr1 = 0, ptr2 = 0; vector<ll> p, q; ll sum_pl = 0, sum_pr = 0; ll sum_ql = 0, sum_qr = 0; { for (auto &it : a) { sum_pr += it.first; sum_qr += it.second; p.pb(it.first); q.pb(it.second); } sort(all(p)); sort(all(q)); } ll ans = LINF; for (ll x : cool) { while (ptr1 < n && p[ptr1] <= x) { sum_pr -= p[ptr1]; sum_pl += p[ptr1]; ptr1++; } while (ptr2 < n && q[ptr2] <= x) { sum_qr -= q[ptr2]; sum_ql += q[ptr2]; ptr2++; } ll cur = 0; cur += (ptr1 * x - sum_pl) + (sum_pr - (n - ptr1) * x); cur += (ptr2 * x - sum_ql) + (sum_qr - (n - ptr2) * x); mini(ans, cur); } ans += total; cout << ans << "\n"; } void run() { cin >> k >> n; rep(i, 0, n) { char t1, t2; ll x1, x2; cin >> t1 >> x1 >> t2 >> x2; if (t1 == t2) { total += abs(x1 - x2); } else { if (t1 > t2) { swap(t1, t2); swap(x1, x2); } a.pb({x1, x2}); cool.pb(x1); cool.pb(x2); } } sort(all(cool)); cool.resize(unique(all(cool)) - cool.begin()); sort(all(a)); n = sz(a); total += n; if (k == 1) { solve1(); return; } ll ans = LINF; for (ll x1 : cool) { for (ll x2 : cool) { ll cur = 0; for (auto &it : a) { ll best = LINF; mini(best, abs(it.first - x1) + abs(it.second - x1)); mini(best, abs(it.first - x2) + abs(it.second - x2)); cur += best; } mini(ans, cur); } } ans += total; cout << ans << "\n"; }
#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...