This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e3 + 10;
//const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, k;
int a[maxN][maxN];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
struct TEdge{
int u, v, c, w;
};
vector <TEdge> S;
vector <int> adj[maxN * maxN];
bool inqueue[maxN * maxN];
int trace[maxN * maxN];
int d[maxN * maxN];
int conv(int x, int y){
if (x > n || y > n || !x || !y) return 0;
return (x - 1) * n + y;
}
void add_edge(int u, int v, int c, int w){
w = -w;
adj[u].pb(S.size());
S.pb({u, v, c, w});
adj[v].pb(S.size());
S.pb({v, u, 0, -w});
}
void MCMF(){
fill(d, d + n * n + 2, inf);
d[0] = 0;
queue <int> Q;
Q.push(0);
while (!Q.empty()){
int u = Q.front();
inqueue[u] = 0;
Q.pop();
for (int i: adj[u]){
int v = S[i].v, c = S[i].c, w = S[i].w;
if (!c || d[v] <= d[u] + w) continue;
d[v] = d[u] + w;
trace[v] = i;
if (!inqueue[v]){
inqueue[v] = 1;
Q.push(v);
}
}
}
}
void Init(){
cin >> n >> k;
int sum = 0;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j){
cin >> a[i][j];
}
}
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j){
sum += a[i][j];
if ((i + j) & 1){
add_edge(conv(i, j), n * n + 1, 1, 0);
continue;
}
add_edge(0, conv(i, j), 1, 0);
for (int k = 0; k < 4; ++k){
int v = conv(i + dx[k], j + dy[k]);
if (!v) continue;
add_edge(conv(i, j), v, 1, a[i][j] + a[i + dx[k]][j + dy[k]]);
}
}
}
while (k--){
MCMF();
int v = n * n + 1;
sum += d[v];
while (v){
int i = trace[v];
S[i].c ^= 1;
S[i ^ 1].c ^= 1;
v = S[i].u;
}
}
cout << sum;
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}
Compilation message (stderr)
domino.cpp: In function 'int main()':
domino.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |