| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1366242 | Ekber_Ekber | Palembang Bridges (APIO15_bridge) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <debug.h>
#else
#define debug(...)
#endif
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+16, MOD = 1e+9 + 7, K = 31;
void _() {
int k, n;
cin >> k >> n;
int res = 0;
vector <pair<int, int>> v;
for (int i = 0; i < n; i++) {
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if (a == b) {
res += abs(x - y);
continue;
}
if (x > y) swap(x, y);
v.pb({x, y});
}
n = v.size();
if (n == 0) {
cout << res;
return;
}
map <int, int> g;
int ls = INF;
for (int i = 0; i < n; i++) {
int l = v[i].ff, r = v[i].ss;
g[l]++;
g[l]++;
g[r]++;
g[r]++;
ls = min(ls, l-1);
}
int s = -2 * n;
int ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(ls - v[i].ff) + abs(ls - v[i].ss);
}
int mn = ans;
for (auto &[x, y] : g) {
// cerr << "From: " << ls << " To: " << x << " Slope: " << s << endl;
// cerr << x << ' ' << y << ' ' << ls << ' ';
ans += (x - ls) * s;
s += y;
mn = min(mn, ans);
ls = x;
// cerr << ans << endl;
}
cout << res + mn + n;
}
signed main() {
GOOD_LUCK
int tests=1;
// cin >> tests;
for (int i=1; i <= tests; i++) {
_();
cout << endl;
}
return 0;
}