結果

問題 No.3306 Life is Easy?
ユーザー Nachia
提出日時 2025-10-05 13:46:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 500 ms / 2,000 ms
コード長 3,207 bytes
コンパイル時間 1,067 ms
コンパイル使用メモリ 95,824 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 13:47:22
合計ジャッジ時間 5,822 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <queue>
#include <utility>

namespace nachia {

struct MinimumCostFlow {
    template<class T>
    using nega_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;

    using cap = long long;
    using cost = long long;
    struct Edge { int to, rev; cap c; cost d; };

    int N;
    int src = 0, snk = 1;
    std::vector<std::vector<Edge>> E;

    cost fAns = 0;
    std::vector<cost> D, P;
    std::vector<int> PE;

    MinimumCostFlow(int n) {
        N = n;
        E.resize(n);
        D.resize(n);
        PE.resize(n);
        P.resize(n);
    }

    void addEdge(int u, int v, cap cap, cost cost) {
        E[u].push_back(Edge{ v, (int)E[v].size(), cap, cost });
        E[v].push_back(Edge{ u, (int)E[u].size() - 1, 0, -cost });
    }

    void dijkstra() {
        for(int i=0; i<N; i++) D[i] = PE[i] = -1;
        nega_queue<std::pair<cost, int>> Q;
        Q.push({ 0, src });
        D[src] = 0;
        while (Q.size()) {
            auto d = Q.top().first;
            int p = Q.top().second;
            Q.pop();
            if (D[p] != d) continue;
            for (Edge e : E[p]) if (e.c != 0) {
                auto nxd = d + e.d + P[p] - P[e.to];
                if (D[e.to] != -1 && D[e.to] <= nxd) continue;
                D[e.to] = nxd;
                PE[e.to] = e.rev;
                Q.push({ nxd, e.to });
            }
        }
        for(int i=0; i<N; i++) if(D[i] != -1) P[i] += D[i];
    }

    cost flow(int xsrc, int xsnk, cap f) {
        src = xsrc;
        snk = xsnk;
        while (f) {
            dijkstra();
            if (D[snk] == -1) { f = 0; fAns = -1; return fAns; }
            int p = snk;
            cap c = f;
            while (p != src) {
                auto& e = E[p][PE[p]];
                if(E[e.to][e.rev].c < c) c = E[e.to][e.rev].c;
                p = e.to;
            }
            p = snk;
            while (p != src) {
                auto& e = E[p][PE[p]];
                auto& re = E[e.to][e.rev];
                e.c += c;
                re.c -= c;
                fAns += c * re.d;
                p = e.to;
            }
            f -= c;
        }
        return fAns;
    }
};

}

void testcase(){
  ll N, M; cin >> N >> M;
  V<V<ll>> A(N, V<ll>(M));
  REP(i,N) REP(j,M) cin >> A[i][j];
  nachia::MinimumCostFlow mcf(N+M+2);
  ll off = 1001001001;
  ll src = N+M, snk = N+M+1;
  REP(i,N/2){
    mcf.addEdge(src, i, 1, 0);
    REP(j,M) mcf.addEdge(i, N+j, 1, A[i][j]);
  }
  REP(i,N/2){
    REP(j,M) mcf.addEdge(N+j, N-1-i, 1, off-A[N-1-i][j]);
    mcf.addEdge(N-1-i, snk, 1, 0);
  }
  ll ans = mcf.flow(src, snk, N/2);
  ans -= off * (N/2);
  ans = -ans;
  cout << ans << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}
0