#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:
vector<int> head, point, next, cost, tr;
vector<short> dist;
vector<char> flow, capa;
int numNode, numEdge;
public:
MaxFlowMinCost(int _n = 0) {
point.clear(), next.clear(), flow.clear();
capa.clear(), cost.clear();
numNode = _n, numEdge = 0;
head.assign(_n + 7, -1);
dist.assign(_n + 7, 0);
tr.assign(_n + 7, 0);
}
void addEdge(int u, int v, int ca, int co) {
point.push_back(v), flow.push_back(0), capa.push_back(ca);
cost.push_back(co), next.push_back(head[u]), head[u] = numEdge++;
point.push_back(u), flow.push_back(0), capa.push_back(0);
cost.push_back(-co), next.push_back(head[v]), head[v] = numEdge++;
}
bool bellmanFord(int s, int t) {
queue<int> qu;
vector<bool> inQu(numNode + 7, 0);
for (int i = 1; i <= numNode; ++i)
dist[i] = 32767, 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 = head[u]; it >= 0; it = next[it]) {
if(flow[it] < capa[it]) {
int v(point[it]);
if(dist[v] > dist[u] + cost[it]) {
dist[v] = dist[u] + cost[it];
tr[v] = it;
if(!inQu[v]) {
inQu[v] = 1;
qu.push(v);
}
}
}
}
}
return (dist[t] < 32767);
}
ii maxFlow(int s, int t) {
for (int i = 0; i < numEdge; ++i)
flow[i] = 0;
int totCost(0);
int totFlow(0);
while(bellmanFord(s, t)) {
int delta(1e9+7);
for (int u = t; u != s; u = point[tr[u] ^ 1])
delta = min(delta, capa[tr[u]] - flow[tr[u]]);
for (int u = t; u != s; u = point[tr[u] ^ 1]) {
flow[tr[u]] += delta;
flow[tr[u] ^ 1] -= 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);
ll 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")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
28236 KB |
Output is correct |
| 2 |
Correct |
71 ms |
28256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1459 ms |
430296 KB |
Output is correct |
| 2 |
Correct |
1365 ms |
430856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
864 ms |
241068 KB |
Output is correct |
| 2 |
Correct |
764 ms |
241120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
108060 KB |
Output is correct |
| 2 |
Correct |
383 ms |
108188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2104 ms |
430236 KB |
Output is correct |
| 2 |
Correct |
1898 ms |
426820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2174 ms |
430252 KB |
Output is correct |
| 2 |
Correct |
1936 ms |
430744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1916 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2294 ms |
430380 KB |
Output is correct |
| 2 |
Correct |
2092 ms |
430740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
596 ms |
108832 KB |
Output is correct |
| 2 |
Correct |
540 ms |
108844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2487 ms |
430208 KB |
Output is correct |
| 2 |
Correct |
2345 ms |
430736 KB |
Output is correct |
