oj.uz

Submission #1018459

# Submission time Handle Problem Language Result Execution time Memory
1018459 2024-07-10T05:27:22 Z caterpillow Domino (COCI15_domino) C++17
110 / 160
 887 ms 524288 KB 
#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;
                    }
                }
            }
        }
        assert(dist[s] == 0);
        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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 37044 KB Output is correct
2 Correct 55 ms 38472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 1 ms 720 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 788 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 333820 KB Output is correct
2 Correct 592 ms 341924 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 143928 KB Output is correct
2 Correct 254 ms 146156 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 818 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 866 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2004 KB Output is correct
2 Correct 3 ms 2004 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 818 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 142736 KB Output is correct
2 Correct 334 ms 146204 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 887 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -