Submission #41393

#TimeUsernameProblemLanguageResultExecution timeMemory
41393NurlykhanPalembang Bridges (APIO15_bridge)C++14
0 / 100
2 ms792 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}; ll solve(vec a, vec b) { int n = sz(a); vec x_arr; for (auto it : a) { x_arr.pb(it); } for (auto it : b) { x_arr.pb(it); } ll ans = LINF; for (auto x : x_arr) { ll cur = 0; for (int i = 0; i < n; 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); } } ans = min(ans, cur); } return ans + n; } int k, n; int main() { int nn; ll ans = 0; cin >> k >> nn; assert(k == 1); vec A, B; for (int i = 1; i <= nn; i++) { char ta, tb; int 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(A, B); 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...