제출 #1265851

#제출 시각아이디문제언어결과실행 시간메모리
1265851canhnam357Palembang Bridges (APIO15_bridge)C++20
22 / 100
26 ms2496 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int T, n; cin >> T >> n; if (T == 1) { long long ans = 0; vector<int> a; for (int i = 0; i < n; i++) { char x, y; int c, d; cin >> x >> c >> y >> d; if (x == y) ans += abs(c - d); else a.push_back(c), a.push_back(d), ans++; } sort(a.begin(), a.end()); for (int i : a) { ans += abs(i - a[a.size() / 2]); } cout << ans << '\n'; } else { vector<pair<int, int>> a; long long ans = 0; for (int i = 0; i < n; i++) { char x, y; int c, d; cin >> x >> c >> y >> d; if (x == y) ans += abs(c - d); else a.emplace_back(c, d), ans++; } sort(a.begin(), a.end(), [&](auto i, auto j) { return i.first + i.second < j.first + j.second; }); n = a.size(); vector<long long> pre(n), suf(n); { long long suml = 0, sumr = 0; multiset<int> r; multiset<int, greater<int>> l; l.insert(INT_MIN); r.insert(INT_MAX); for (int i = 0; i < n; i++) { auto [x, y] = a[i]; if (x > *l.begin()) r.insert(x), sumr += x; else l.insert(x), suml += x; if (y > *l.begin()) r.insert(y), sumr += y; else l.insert(y), suml += y; while (r.size() - 1 > l.size()) { int x = *r.begin(); r.erase(r.begin()); sumr -= x; suml += x; l.insert(x); } pre[i] = sumr - (r.size() - 1LL) * *r.begin() + (l.size() - 1LL) * *r.begin() - suml; } } { long long suml = 0, sumr = 0; multiset<int> r; multiset<int, greater<int>> l; l.insert(INT_MIN); r.insert(INT_MAX); for (int i = n - 1; i >= 0; i--) { auto [x, y] = a[i]; if (x > *l.begin()) r.insert(x), sumr += x; else l.insert(x), suml += x; if (y > *l.begin()) r.insert(y), sumr += y; else l.insert(y), suml += y; while (r.size() - 1 > l.size()) { int x = *r.begin(); r.erase(r.begin()); sumr -= x; suml += x; l.insert(x); } suf[i] = sumr - (r.size() - 1LL) * *r.begin() + (l.size() - 1LL) * *r.begin() - suml; } } if (n > 0) { long long add = min(pre[n - 1], suf[0]); for (int i = 1; i < n; i++) { add = min(add, pre[i - 1] + suf[i]); } ans += add; } cout << ans << '\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...