제출 #41398

#제출 시각아이디문제언어결과실행 시간메모리
41398NurlykhanPalembang Bridges (APIO15_bridge)C++14
22 / 100
193 ms2404 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() #define vec vector<int> #define dead not_bad #define bad gooood #define left not_right #define y1 what using namespace std; const int N = (int) 2e5 + 10; const int M = (int) 2e6; const ll LINF = (ll) 2e18; const int INF = (int) 1e9 + 7; const int ALPHA = 26; const int mod = INF; const double PI = 3.14159265359; const ld EPS = (ld) 1e-12; const int nx[4] = {0, 0, -1, 1}; const int ny[4] = {1, -1, 0, 0}; vector<ll> a, b; ll get(ll x) { ll cur = 0; for (int i = 0; i < sz(a); i++) { if (a[i] <= x && x <= b[i]) { cur += b[i] - a[i]; } else if (a[i] > x) { cur += a[i] + b[i] - 2 * x; } else if (b[i] < x) { cur += 2 * x - (a[i] + b[i]); } else { assert(0); } } return cur; } ll solve() { ll l = 0, r = INF; while (r - l > 2) { ll m1 = l + (r - l) / 3; ll m2 = r - (r - l) / 3; if (get(m1) > get(m2)) { l = m1; } else { r = m2; } } ll ans = LINF; for (ll i = l; i <= r; i++) { ans = min(ans, get(i)); } return ans + sz(a); } int k, n; int main() { #define fn "teams" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else //freopen(fn".in", "r", stdin); //freopen(fn".out", "w", stdout); #endif ll ans = 0; cin >> k >> n; for (int i = 1; i <= n; i++) { char ta, tb; ll x1, x2; cin >> ta >> x1 >> tb >> x2; //cout << ta << ' ' << x1 << ' ' << tb << ' ' << x2 << endl; if (x1 > x2) swap(x1, x2); if (ta == tb) { ans += x2 - x1; } else { a.pb(x1); b.pb(x2); } } cout << ans + solve(); 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...