Submission #1018454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018454		caterpillow	Domino (COCI15_domino)	C++17	110 / 160	895 ms	524288 KiB

domino

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

max cost max flow?

*/

struct Queue {
    int i = 0;
    vt<int> q;
    int pop() {
        return q[i++];
    }
    void push(int v) {
        q.pb(v);
    }
    bool empty() {
        return i == size(q);
    }
};

struct Edge {
    int u, v;
    int flo, cost;
};

// max cost
struct MCMF {
    int n;
    vt<Edge> edges;  
    vt<vt<int>> adj;
    void init(int _n) {
        n = _n;
        adj.resize(n);
    }
    void ae(int u, int v, int cost) {
        int ei = size(edges);
        edges.pb({u, v, 0, cost});
        adj[u].pb(ei);
        adj[v].pb(~ei);
    }
    bool valid(int ei) {
        if (ei >= 0) return edges[ei].flo == 0;
        else return edges[~ei].flo == 1;
    }
    pi get_edge(int u, int ei) {
        if (ei >= 0) return {edges[ei].v, edges[ei].cost};
        else return {edges[~ei].u, -edges[~ei].cost};
    }
    int find_augmenting_path(int s, int t) {
        vt<int> par(n, -1); // parent edge
        vt<int> dist(n, inf);
        dist[s] = 0;
        vt<bool> in_queue(n);
        Queue q;
        q.push(s);
        while (!q.empty()) {
            int u = q.pop();
            in_queue[u] = false;
            for (int ei : adj[u]) {
                if (!valid(ei)) continue;
                auto [v, cost] = get_edge(u, ei);
                if (dist[u] + cost < dist[v]) {   
                    dist[v] = dist[u] + cost;
                    par[v] = ei;
                    if (!in_queue[v]) {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }
        int u = t;
        while (par[u] != -1) {
            if (par[u] >= 0) edges[par[u]].flo = 1, u = edges[par[u]].u;
            else edges[~par[u]].flo = 0, u = edges[~par[u]].v;
        }
        return dist[t];
    }
    int calc(int s, int t, int k) {
        int ans = 0;
        F0R (_, k) ans += find_augmenting_path(s, t);
        return ans;
    }
};

int n, k; 
vt<vt<int>> grid;
MCMF mcmf;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> k;
    grid.resize(n, vt<int>(n));
    ll tot = 0;
    F0R (r, n) {
        F0R (c, n) {
            cin >> grid[r][c];
            tot += grid[r][c];
        }
    }
    mcmf.init(n * n + 2);
    int s = n * n;
    int t = s + 1;
    const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    auto enc = [&] (int r, int c) { return r * n + c; };
    F0R (r, n) {
        F0R (c, n) {
            if ((r + c) % 2 == 0) continue;
            F0R (i, 4) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n) {
                    mcmf.ae(enc(r, c), enc(nr, nc), 0);
                }
            }
        }
    }
    F0R (r, n) {
        F0R (c, n) {
            if ((r + c) % 2 == 1) mcmf.ae(s, enc(r, c), 1000 - grid[r][c]);
            else mcmf.ae(enc(r, c), t, 1000 - grid[r][c]);
        }
    }
    int flow = mcmf.calc(s, t, k);
    int ans = 2 * k * 1000 - flow;
    cout << tot - ans << endl;
}

Compilation message (stderr)

domino.cpp:135:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main() {
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 0 / 10