#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;
typedef pair<int, ll> il;
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:
struct Edge {
int from, to, flow, capa, cost;
Edge(int _f = 0, int _t = 0, int _ca = 0, int _co = 0) {
from = _f, to = _t, flow = 0, capa = _ca, cost = _co;
}
inline int residual(void) {
return capa - flow;
}
};
vector<Edge> E;
vector<vector<int>> adj;
vector<ll> dist;
vector<int> tr;
int numNode;
public:
MaxFlowMinCost(int _n = 0) {
E.clear();
adj.assign(_n + 7, vector<int>());
numNode = _n;
dist.assign(_n + 7, 0);
tr.assign(_n + 7, 0);
}
void addEdge(int u, int v, int ca, int co) {
adj[u].push_back(E.size());
E.push_back({u, v, ca, co});
adj[v].push_back(E.size());
E.push_back({v, u, 0, -co});
}
bool bellmanFord(int s, int t) {
queue<int> qu;
vector<bool> inQu(numNode + 7, 0);
for (int i = 1; i <= numNode; ++i)
dist[i] = 1e18, 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 : adj[u]) {
if(E[it].residual() > 0) {
int v(E[it].to);
if(dist[v] > dist[u] + E[it].cost) {
dist[v] = dist[u] + E[it].cost;
tr[v] = it;
if(!inQu[v]) {
inQu[v] = 1;
qu.push(v);
}
}
}
}
}
return (dist[t] < 1e18);
}
il maxFlow(int s, int t) {
for (int i = 0; i < int(E.size()); ++i)
E[i].flow = 0;
ll totCost(0);
int totFlow(0);
while(bellmanFord(s, t)) {
int delta(1e9+7);
for (int u = t; u != s; u = E[tr[u]].from)
delta = min(delta, E[tr[u]].residual());
for (int u = t; u != s; u = E[tr[u]].from) {
E[tr[u]].flow += delta;
E[tr[u] ^ 1].flow -= 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")
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
113 ms |
61984 KB |
Output is correct |
| 2 |
Correct |
110 ms |
61992 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1200 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
567 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1364 ms |
486796 KB |
Output is correct |
| 2 |
Correct |
1221 ms |
487148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
653 ms |
242720 KB |
Output is correct |
| 2 |
Correct |
635 ms |
242804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
551 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1072 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
556 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
2792 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
596 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1644 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
987 ms |
241016 KB |
Output is correct |
| 2 |
Correct |
833 ms |
240980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
582 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
