結果

問題 No.1324 Approximate the Matrix
ユーザー pes_magicpes_magic
提出日時 2020-12-21 22:52:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 3,929 bytes
コンパイル時間 1,383 ms
コンパイル使用メモリ 95,784 KB
実行使用メモリ 72,064 KB
最終ジャッジ日時 2024-09-21 13:12:06
合計ジャッジ時間 5,833 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 211 ms
71,936 KB
testcase_04 AC 211 ms
72,064 KB
testcase_05 AC 211 ms
72,064 KB
testcase_06 AC 208 ms
71,936 KB
testcase_07 AC 211 ms
72,064 KB
testcase_08 AC 57 ms
43,904 KB
testcase_09 AC 17 ms
12,032 KB
testcase_10 AC 43 ms
26,496 KB
testcase_11 AC 82 ms
44,416 KB
testcase_12 AC 10 ms
7,680 KB
testcase_13 AC 11 ms
9,216 KB
testcase_14 AC 101 ms
56,960 KB
testcase_15 AC 55 ms
39,808 KB
testcase_16 AC 3 ms
6,940 KB
testcase_17 AC 31 ms
14,848 KB
testcase_18 AC 17 ms
13,056 KB
testcase_19 AC 5 ms
6,944 KB
testcase_20 AC 13 ms
11,648 KB
testcase_21 AC 4 ms
6,944 KB
testcase_22 AC 46 ms
38,784 KB
testcase_23 AC 14 ms
6,944 KB
testcase_24 AC 94 ms
41,856 KB
testcase_25 AC 39 ms
16,640 KB
testcase_26 AC 42 ms
20,736 KB
testcase_27 AC 10 ms
6,944 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,944 KB
testcase_36 AC 2 ms
6,944 KB
testcase_37 AC 252 ms
72,064 KB
testcase_38 AC 248 ms
72,064 KB
testcase_39 AC 247 ms
72,064 KB
testcase_40 AC 250 ms
71,936 KB
testcase_41 AC 256 ms
72,064 KB
testcase_42 AC 87 ms
71,936 KB
testcase_43 AC 87 ms
71,936 KB
testcase_44 AC 86 ms
71,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

template<typename CAP, typename COST>
class MinCostFlow {
public:
    explicit MinCostFlow(int N) : g(N) {}
    void addEdge(int src, int dst, CAP cap, const vector<COST>& cost){
        int r1 = g[src].size();
        int r2 = g[dst].size();
        g[src].emplace_back(src, dst, cap, cost, r2);
        g[dst].emplace_back(dst, src, 0, cost, r1);
    }
    pair<COST, CAP> solve(int s, int t, CAP maxFlow){
        const int n = g.size();
        pair<COST, CAP> res = make_pair(0, 0);
        vector<COST> h(n, 0);
        while(maxFlow > 0){
            vector<COST> dist(n, INF); dist[s] = 0;
            vector<pair<int, int>> prev(n, make_pair(-1, -1));
            priority_queue<pair<COST, int>, vector<pair<COST, int>>, greater<pair<COST, int>>> qu;
            qu.emplace(0, s);
            while(!qu.empty()){
                auto e = qu.top(); qu.pop();
                if(dist[e.second] < e.first) continue;
                for(int i=0;i<g[e.second].size();i++){
                    auto& p = g[e.second][i];
                    if(p.cap > 0 && dist[p.dst] > dist[p.src] + p.cost() + h[p.src] - h[p.dst]){
                        dist[p.dst] = dist[p.src] + p.cost() + h[p.src] - h[p.dst];
                        prev[p.dst] = make_pair(p.src, i);
                        qu.emplace(dist[p.dst], p.dst);
                    }
                }
            }
            if(prev[t].first == -1) break;
            CAP f = maxFlow;
            for(int u=t;u!=s;u=prev[u].first) f = min(f, g[prev[u].first][prev[u].second].cap);
            for(int u=t;u!=s;u=prev[u].first){
                auto& p = g[prev[u].first][prev[u].second];
                auto& q = g[p.dst][p.rev];
                res.first += f * p.cost();
                p.cap -= f;
                q.cap += f;
            }
            res.second += f;
            for(int i=0;i<n;i++) h[i] += dist[i];
            maxFlow -= f;
        }
        return res;
    }
private:
    class Edge {
    public:
        explicit Edge(int src, int dst, CAP cap, const vector<COST>& costVec, int rev) : src(src), dst(dst), cap(cap), costVec(costVec), rev(rev) {}
        const int src;
        const int dst;
        CAP cap;
        const int rev;
        COST cost(){
            if(src < dst && costVec.size() - cap < 0) assert(false);
            if(src > dst && cap - 1 < 0) assert(false);
            return src < dst ? costVec[costVec.size()-cap] : -costVec[cap-1];
        }
    private:
        vector<COST> costVec;
    };
private:
    const COST INF = 1LL << 30;
    vector<vector<Edge>> g;
};

int main(){
    int N, K;
    while(cin >> N >> K){
        vector<int> A(N), B(N);
        vector P(N, vector(N, 0));
        for(auto& t : A) cin >> t;
        for(auto& t : B) cin >> t;
        int base = 0;
        for(auto& v : P){
            for(auto& t : v){
                cin >> t;
                base += t*t;
            }
        }
        MinCostFlow<int, int> mcf(2*N+2);
        for(int i=0;i<N;i++){
            if(A[i] > 0){
                vector<int> v(A[i], 0);
                mcf.addEdge(0, i+1, A[i], v);
            }
        }
        for(int i=0;i<N;i++){
            if(B[i] > 0){
                vector<int> v(B[i], 0);
                mcf.addEdge(N+1+i, 2*N+1, B[i], v);
            }
        }
        const int THR = 40000;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                vector<int> v(200);
                for(int k=0;k<200;k++){
                    int c1 = P[i][j] - k;
                    int c2 = P[i][j] - (k+1);
                    v[k] = c2*c2 - c1*c1 + THR;
                }
                mcf.addEdge(i+1, N+j+1, 200, v);
            }
        }
        for(int i=0;i<K;i++){
            base += mcf.solve(0, 2*N+1, 1).first - THR;
        }
        cout << base << endl;
    }
}
0