結果
問題 |
No.1028 闇討ち
|
ユーザー |
|
提出日時 | 2025-05-30 00:08:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 411 ms / 2,000 ms |
コード長 | 1,758 bytes |
コンパイル時間 | 1,427 ms |
コンパイル使用メモリ | 124,672 KB |
実行使用メモリ | 16,256 KB |
最終ジャッジ日時 | 2025-05-30 00:08:41 |
合計ジャッジ時間 | 5,926 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1028 #include <iostream> #include <vector> #include <algorithm> #include <functional> #include <queue> /// @brief slope trick template <class T> struct slope_trick { T min_f; std::priority_queue<T> l; std::priority_queue<T, std::vector<T>, 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<T, std::vector<T>, std::greater<>>(); } void min_r() { l = std::priority_queue<T>(); } }; 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<slope_trick<int>> 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; }