제출 #389769

#제출 시각아이디문제언어결과실행 시간메모리
389769milleniumEeeePalembang Bridges (APIO15_bridge)C++14
22 / 100
83 ms7492 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); #define int long long using namespace std; const int MAXN = (int)2e5 + 5; const int INF = 1e18; pair <char, int> st[MAXN]; pair <char, int> fn[MAXN]; bool ok(int pos) { return (st[pos].first == fn[pos].first); } vector <int> vec; int check(int pos) { int sum = 0; for (int el : vec) { sum += abs(el - pos); } return sum; } signed main() { fastInp; int n, k; cin >> k >> n; assert(k == 1); int side = 0; int cnt = 0; for (int i = 1; i <= n; i++) { cin >> st[i].fr >> st[i].sc >> fn[i].fr >> fn[i].sc; if (ok(i)) { side += abs(st[i].sc - fn[i].sc); } else { cnt++; vec.pb(st[i].sc); vec.pb(fn[i].sc); } } sort(all(vec)); int l = 0, r = 1e9; while (r - l > 3) { int m1 = l + (r - l) / 3; int m2 = r - (r - l) / 3; if (check(m1) < check(m2)) { r = m2; } else { l = m1; } } int bridge = INF; for (int i = l; i <= r; i++) { bridge = min(bridge, check(i) + cnt); } cout << side + bridge; } /* 2 5 B 0 A 4 B 1 B 3 A 5 B 7 B 2 A 6 B 1 A 7 */
#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...