This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define fs first
#define sc second
ll n, k, g[MAXN][MAXN], r, s = 0, m;
vector<pair<ll, pair<pair<ll, ll>, bool>>> d;
bool v[MAXN][MAXN];
void recurse(ll itr = 0, ll i = -1, ll sm = 0){
if(itr == k){
r = min(r, s - sm);
return;
}
FOR(i2, i + 1, m - 1){
if(v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] || v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc]){
continue;
}
v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = true;
v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = true;
recurse(itr + 1, i2, sm + d[i2].fs);
v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = false;
v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = false;
}
}
int main(){
cin >> n >> k;
FOR(i, 1, n) FOR(j, 1, n) {
cin >> g[i][j];
v[i][j] = false;
s += g[i][j];
}
r = s;
FOR(i, 1, n) FOR(j, 1, n) {
if(i != n) d.push_back({g[i][j] + g[i + 1][j], {{i, j}, 0}});
if(j != n) d.push_back({g[i][j] + g[i][j + 1], {{i, j}, 1}});
}
sort(begin(d), end(d));
reverse(begin(d), end(d));
m = min((k - 1) * 6 + 1, 2 * n * (n - 1));
recurse();
cout << r << endl;
}
# | 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... |