#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" #define NDEBUG #define SHOW(...) static_cast(0) //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// template T read() { T v; return std::cin >> v, v; } template std::vector readVec(const std::size_t l) { std::vector v(l); for (auto& e : v) { std::cin >> e; } return v; } using ld = long double; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr unsigned int MOD = 1000000007; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr F PI = static_cast(3.1415926535897932385); std::mt19937 mt{std::random_device{}()}; template bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); } template bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T popCount(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : (T)__builtin_popcountll(u); #else unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); #endif } template constexpr T log2p1(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : T(64 - __builtin_clzll(u)); #else unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v); #endif } template constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); } template constexpr T msbp1(const T v) { return log2p1(v); } template constexpr T lsbp1(const T v) { #ifdef __has_builtin return __builtin_ffsll(v); #else return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1); #endif } template constexpr bool ispow2(const T v) { return popCount(v) == 1; } template constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); } //!==============================================================================!// //! dP dP oo 88888888b oo dP !// //! 88 88 88 88 !// //! 88 88 88d888b. dP .d8888b. 88d888b. a88aaaa dP 88d888b. .d888b88 !// //! 88 88 88' '88 88 88' '88 88' '88 88 88 88' '88 88' '88 !// //! Y8. .8P 88 88 88 88. .88 88 88 88 88 88 88 88. .88 !// //! 'Y88888P' dP dP dP '88888P' dP dP dP dP dP dP '88888P8 !// //!==============================================================================!// class UnionFind { public: UnionFind(const std::size_t v) : V(v), parent(v), size(v, 1) { std::iota(parent.begin(), parent.end(), 0); } std::size_t find(const std::size_t a) { return assert(a < V), parent[a] == a ? a : parent[a] = find(parent[a]); } bool same(const std::size_t a, const std::size_t b) { assert(a < V), assert(b < V); return find(a) == find(b); } void unite(std::size_t a, std::size_t b) { assert(a < V), assert(b < V); a = find(a), b = find(b); if (a == b) { return; } if (size[a] < size[b]) { std::swap(a, b); } size[a] += size[b], parent[b] = a; } std::size_t getSize(const std::size_t a) { return assert(a < V), size[find(a)]; } friend std::ostream& operator<<(std::ostream& os, const UnionFind& uf) { os << "["; for (std::size_t i = 0; i < uf.parent.size(); i++) { os << uf.parent[i] << (i + 1 == uf.parent.size() ? "" : ","); } return (os << "]\n"); } private: const std::size_t V; std::vector parent, size; }; //!=====================================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 .d8888b. dP 88d888b. !// //! 88 88 88 88' '88 88 88' '88 !// //! 88 88 88 88. .88 88 88 88 !// //! dP dP dP '88888P8 dP dP dP !// //!=====================================!// int main() { constexpr int N = 5; auto C = Vec(N, N, 0LL); ll S = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { std::cin >> C[i][j], S += C[i][j]; } } std::vector memo(1 << (N * N), false); ll ans = S; auto score = [&](auto&& self, const int mask) -> void { if (mask + 1 == (1 << (N * N))) { return; } auto use = Vec(N, N, false); int pc = N * N; ll us = 0; std::vector up; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { use[i][j] = (mask & (1 << (N * i + j))) == 0, pc -= use[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (use[i][j]) { us += C[i][j]; if (0 < i and not use[i - 1][j]) { up.push_back(N * i + j); } if (0 < j and not use[i][j - 1]) { up.push_back(N * i + j); } if (i < 4 and not use[i + 1][j]) { up.push_back(N * i + j); } if (j < 4 and not use[i][j + 1]) { up.push_back(N * i + j); } } } } const ll score = std::abs(S - 2 * us); UnionFind uf(N * N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j < 4 and use[i][j] and use[i][j + 1]) { uf.unite(N * i + j, N * i + j + 1); } if (i < 4 and use[i][j] and use[i + 1][j]) { uf.unite(N * i + j, N * (i + 1) + j); } } } const int y = up.front() / N, x = up.front() % N; if (uf.getSize(N * y + x) + pc < N * N) { return; } chmin(ans, score); for (const int p : up) { if (not memo[mask | (1 << p)]) { self(self, mask | (1 << p)); } } memo[mask] = true; }; score(score, 1); std::cout << ans << std::endl; return 0; }