// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1028 #include #include #include #include #include /// @brief slope trick template struct slope_trick { T min_f; std::priority_queue l; std::priority_queue, std::greater<>> r; slope_trick() : min_f(), l(), r() {} T get_x() { return l.top(); } T get() { return min_f; } T get_y() { return get(); } /// @brief Add f(x) = a void add(T a) { min_f += a; } /// @brief Add f(x) = max(0, x - a) void add_f(T a) { if (!l.empty()) min_f += std::max(T(), l.top() - a); l.emplace(a); auto x = l.top(); l.pop(); r.emplace(x); } /// @brief Add f(x) = max(0, a - x) void add_g(T a) { if (!r.empty()) min_f += std::max(T(), a - r.top()); r.emplace(a); auto x = r.top(); r.pop(); l.emplace(x); } /// @brief Add f(x) = abs(x - a) = max(0, x - a) + max(0, a - x) void add_abs(T a) { add_f(a); add_g(a); } void min_l() { r = std::priority_queue, std::greater<>>(); } void min_r() { l = std::priority_queue(); } }; int main(void) { int n; std::cin >> n; std::vector a(n, std::vector(n, 0)); for (auto &v : a) { for (auto &e : v) std::cin >> e; } std::vector> v(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { v[a[i][j] - 1].add(j); v[a[i][j] - 1].add_f(i + j); v[a[i][j] - 1].add_g(i - j); } } int ans = 0; for (int i = 0; i < n; ++i) ans += v[i].get(); std::cout << ans << '\n'; return 0; }