#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?
*/
int n, k;
vt<vt<int>> grid;
bool flo[2000][2000][5]; // direction index, then to source/sink
const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
int enc(int r, int c) {
return r * n + c;
}
pi dec(int id) {
return {id / n, id % n};
}
bool valid(int r, int c) {
return r >= 0 && c >= 0 && r < n && c < n;
}
// sink goes to even r + c
// you never go to the source twice
int find_augmenting_path() {
vt<int> par(n * n, -1); // direction taken to reach here
vt<int> dist(n * n, inf);
vt<bool> in_queue(n * n);
queue<pi> q;
int ans = inf;
pi best;
F0R (r, n) {
F0R (c, n) {
if ((r + c) % 2 == 0) {
if (!flo[r][c][4]) {
int id = enc(r, c);
in_queue[id] = true;
q.push({r, c});
dist[id] = grid[r][c];
par[id] = -1;
}
}
}
}
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
int id = r * n + c;
in_queue[id] = false;
if ((r + c) % 2 == 0) { // lhs
F0R (i, 4) {
int nr = r + dr[i];
int nc = c + dc[i];
if (valid(nr, nc)) {
if (!flo[r][c][i]) { // no flow
int vid = enc(nr, nc);
if (dist[id] < dist[vid]) {
dist[vid] = dist[id];
par[vid] = i;
if (!in_queue[vid]) {
q.push({nr, nc});
in_queue[vid] = true;
}
}
}
}
}
} else { // rhs
F0R (i, 4) {
int nr = r + dr[i];
int nc = c + dc[i];
if (valid(nr, nc)) {
if (flo[nr][nc][(i + 2) % 4]) { // yes flow
int vid = enc(nr, nc);
if (dist[id] < dist[vid]) {
dist[vid] = dist[id];
par[vid] = i;
if (!in_queue[vid]) {
q.push({nr, nc});
in_queue[vid] = true;
}
}
}
}
}
if (!flo[r][c][4]) { // check flow to sink
if (dist[id] + grid[r][c] < ans) {
ans = dist[id] + grid[r][c];
best = {r, c};
}
}
}
}
auto [r, c] = best;
flo[r][c][4] = 1;
while (par[enc(r, c)] != -1) {
int id = enc(r, c);
int i = (par[id] + 2) % 4; // direction from current to prev
int pr = r + dr[i];
int pc = c + dc[i];
if ((r + c) % 2 == 0) { // lhs
flo[r][c][i] = 0; // took a backedge
} else { // rhs
flo[pr][pc][par[id]] = 1; // took a normal edge
}
r = pr;
c = pc;
}
flo[r][c][4] = 1;
return ans;
}
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];
grid[r][c] = 1000 - grid[r][c];
}
}
int flow = 0;
F0R (i, k) flow += find_augmenting_path();
int ans = 2 * k * 1000 - flow;
cout << tot - ans << endl;
}
Compilation message
domino.cpp:159:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
159 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
64548 KB |
Output is correct |
| 2 |
Correct |
323 ms |
80480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
36408 KB |
Output is correct |
| 2 |
Correct |
207 ms |
36404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
109 ms |
16452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
653 ms |
64812 KB |
Output is correct |
| 2 |
Correct |
546 ms |
76448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
724 ms |
64816 KB |
Output is correct |
| 2 |
Correct |
597 ms |
80512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
4 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
868 ms |
64528 KB |
Output is correct |
| 2 |
Correct |
687 ms |
80408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
233 ms |
16448 KB |
Output is correct |
| 2 |
Correct |
229 ms |
16468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
64532 KB |
Output is correct |
| 2 |
Correct |
781 ms |
80296 KB |
Output is correct |
