# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
937395 | 2024-03-04T02:03:56 Z | duckindog | Palembang Bridges (APIO15_bridge) | C++17 | 1 ms | 2632 KB |
//from duckindog wth depression #include<bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int k, n; int a[N], b[N]; long long da[N], db[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); if (fopen("duck.inp", "r")) { freopen("duck.inp", "r", stdin); freopen("duck.out", "w", stdout); } cin >> k >> n; long long answer = 0; for (int i = 1; i <= n; ++i) { char A, B; cin >> A >> a[i] >> B >> b[i]; if (A != B) continue; answer += abs(b[i] - a[i]); i -= 1; n -= 1; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); set<int> pos; for (int i = 1; i <= n; ++i) { pos.insert(a[i]); pos.insert(b[i]); da[i] = da[i - 1] + a[i]; db[i] = db[i - 1] + b[i]; } auto cal = [&](int i) { auto itA = upper_bound(a + 1, a + n + 1, i) - a - 1, itB = upper_bound(b + 1, b + n + 1, i) - b - 1; long long ret = 0; ret += 1ll * itA * i - da[itA] + da[n] - da[itA] - 1ll * i * (n - itA); ret += 1ll * itB * i - db[itB] + db[n] - db[itB] - 1ll * i * (n - itB); return ret; }; long long ret = 1'000'000'000'000'000; for (const auto& i : pos) { if (i == *pos.begin()) continue; int l = *prev(pos.lower_bound(i)); int r = i, it = l; while (l <= r) { int mid = l + r >> 1; if (cal(mid) >= cal(mid + 1)) l = it = mid + 1; else r = mid - 1; } ret = min(ret, cal(it)); } cout << answer + ret + n << "\n"; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2632 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |