#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);
F0R (i, n - 2) adj[i].reserve(4);
adj[n - 2].reserve(n / 2);
adj[n - 1].reserve(n / 2);
}
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]);
}
}
return 0;
int flow = mcmf.calc(s, t, k);
int ans = 2 * k * 1000 - flow;
cout << tot - ans << endl;
}
Compilation message
domino.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
138 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
33460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
735 ms |
519360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
290300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
170 ms |
130728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
753 ms |
519532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
763 ms |
519356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
743 ms |
519508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
130984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
759 ms |
519576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
