// File coincollecting.cpp created on 02.10.2025 at 11:58:40
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr i64 inf = i64(1E18);
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
std::vector<std::array<int, 2>> A(N * 2);
for (int i = 0; i < N * 2; ++i) {
std::cin >> A[i][0] >> A[i][1];
--A[i][0], --A[i][1];
}
i64 ans = 0;
for (int i = 0; i < N * 2; ++i) {
int x, y;
if (A[i][0] < 0) {
x = 0;
} else if (A[i][0] < N) {
x = A[i][0];
} else {
x = N - 1;
}
if (A[i][1] <= 0) {
y = 0;
} else {
y = 1;
}
ans += std::abs(x - A[i][0]) + std::abs(y - A[i][1]);
A[i][0] = x;
A[i][1] = y;
debug(x, y);
}
std::vector<std::vector<int>> g(2);
for (int i = 0; i < N * 2; ++i) {
g[A[i][1]].emplace_back(A[i][0]);
}
std::sort(g[0].begin(), g[0].end());
std::sort(g[1].begin(), g[1].end());
int n = int(g[0].size());
int m = int(g[1].size());
std::vector<std::vector<i64>> f(n + 1, std::vector<i64>(m + 1, inf));
f[0][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (f[i][j] == inf) {
continue;
}
debug(i, j, f[i][j]);
int k = (i + j) >> 1;
if (i + 2 <= n && j + 0 <= m) {
int cost = std::abs(g[0][i] - k) + std::abs(g[0][i + 1] - k) + 1;
debug(cost, std::abs(g[0][i] - k), std::abs(g[0][i + 1] - k));
chmin(f[i + 2][j + 0], f[i][j] + cost);
}
if (i + 1 <= n && j + 1 <= m) {
int cost = std::abs(g[0][i] - k) + std::abs(g[1][j] - k);
chmin(f[i + 1][j + 1], f[i][j] + cost);
}
if (i + 0 <= n && j + 2 <= m) {
int cost = std::abs(g[1][j] - k) + std::abs(g[1][j + 1] - k) + 1;
chmin(f[i + 0][j + 2], f[i][j] + cost);
}
}
}
debug(f[n][m]);
ans += f[n][m];
std::cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |