oj.uz

답안 #696125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696125 2023-02-05T15:33:55 Z Nhoksocqt1 Domino (COCI15_domino) C++17
110 / 160
 1369 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int lx[] = {-1, 0, 0, 1}, ly[] = {0, -1, 1, 0};

class MaxFlowMinCost {
    private:
        struct Edge {
            int from, to, flow, capa, cost;

            Edge(int _f = 0, int _t = 0, int _ca = 0, int _co = 0) {
                from = _f, to = _t, flow = 0, capa = _ca, cost = _co;
            }

            inline int residual(void) {
                return capa - flow;
            }
        };

        vector<Edge> E;
        vector<vector<int>> adj;
        vector<ll> dist;
        vector<int> tr;
        int numNode;

    public:
        MaxFlowMinCost(int _n = 0) {
            E.clear();
            adj.assign(_n + 7, vector<int>());
            numNode = _n;

            dist.assign(_n + 7, 0);
            tr.assign(_n + 7, 0);
        }

        void addEdge(int u, int v, int ca, int co) {
            adj[u].push_back(E.size());
            E.push_back({u, v, ca, co});

            adj[v].push_back(E.size());
            E.push_back({v, u, 0, -co});
        }

        bool bellmanFord(int s, int t) {
            queue<int> qu;
            vector<bool> inQu(numNode + 7, 0);
            for (int i = 1; i <= numNode; ++i)
                dist[i] = 1e18, inQu[i] = 0;

            inQu[s] = 1, dist[s] = 0;
            qu.push(s);

            while(qu.size()) {
                int u(qu.front());
                qu.pop();

                inQu[u] = 0;
                for (int it : adj[u]) {
                    if(E[it].residual() > 0) {
                        int v(E[it].to);
                        if(dist[v] > dist[u] + E[it].cost) {
                            dist[v] = dist[u] + E[it].cost;
                            tr[v] = it;

                            if(!inQu[v]) {
                                inQu[v] = 1;
                                qu.push(v);
                            }
                        }
                    }
                }
            }

            return (dist[t] < 1e18);
        }

        ii maxFlow(int s, int t) {
            for (int i = 0; i < int(E.size()); ++i)
                E[i].flow = 0;

            int totFlow(0), totCost(0);
            while(bellmanFord(s, t)) {
                int delta(1e9+7);
                for (int u = t; u != s; u = E[tr[u]].from)
                    delta = min(delta, E[tr[u]].residual());

                for (int u = t; u != s; u = E[tr[u]].from) {
                    E[tr[u]].flow += delta;
                    E[tr[u] ^ 1].flow -= delta;
                }

                totFlow += delta;
                totCost += dist[t] * delta;
            }

            return {totFlow, totCost};
        }
} G;

const int MAXN = 2003;

int val[MAXN][MAXN], nSize, k;

void process() {
    cin >> nSize >> k;

    G = MaxFlowMinCost(nSize * nSize + 3);
    G.addEdge(nSize * nSize + 3, nSize * nSize + 1, k, 0);

    int sum(0);
    for (int i = 1; i <= nSize; ++i) {
        for (int j = 1; j <= nSize; ++j) {
            cin >> val[i][j];
            sum += val[i][j];
            if((i + j) & 1) {
                G.addEdge(nSize * nSize + 1, (i - 1) * nSize + j, 1, -val[i][j]);
                for (int id = 0; id < 4; ++id) {
                    int x(i + lx[id]), y(j + ly[id]);
                    if(x < 1 || y < 1 || x > nSize || y > nSize)
                        continue;

                    G.addEdge((i - 1) * nSize + j, (x - 1) * nSize + y, 1, 0);
                }
            } else {
                G.addEdge((i - 1) * nSize + j, nSize * nSize + 2, 1, -val[i][j]);
            }
        }
    }

    cout << sum + G.maxFlow(nSize * nSize + 3, nSize * nSize + 2).se;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("domino.inp", "r", stdin);
//    freopen("domino.out", "w", stdout);

    process();
    return 0;
}

Compilation message

domino.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
domino.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 62012 KB Output is correct
2 Correct 126 ms 62004 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1072 KB Output is correct
2 Correct 2 ms 1072 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 578 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1369 ms 491936 KB Output is correct
2 Correct 1212 ms 490620 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 664 ms 243532 KB Output is correct
2 Correct 671 ms 243696 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 602 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1072 KB Output is correct
2 Correct 2 ms 1072 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 640 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2792 KB Output is correct
2 Correct 8 ms 2796 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 560 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1644 KB Output is correct
2 Correct 5 ms 1644 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 952 ms 243532 KB Output is correct
2 Correct 851 ms 243704 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #16
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 565 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -