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(int i = a; i <= b; ++i)
#define fs first
#define sc second
ll r, s = 0;
int n, k, g[MAXN][MAXN], m;
set<pair<ll, pair<pair<int, int>, bool>>> sd;
vector<pair<ll, pair<pair<int, int>, bool>>> d;
bool v[MAXN][MAXN];
void recurse(int itr = 0, int 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) {
if(sd.size() < (k - 1) * 7 + 1){
sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
}else if(g[i][j] + g[i + 1][j] > (*sd.begin()).fs){
sd.erase(*sd.begin());
sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
}
}
if(j != n) {
if(sd.size() < (k - 1) * 7 + 1){
sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
}else if(g[i][j] + g[i][j + 1] > (*sd.begin()).fs){
sd.erase(*sd.begin());
sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
}
}
}
for(auto i : sd) {
d.push_back(i);
}
m = sd.size();
recurse();
cout << r << endl;
}
/*
5
6
6
8
9
9
9
10
*/
Compilation message (stderr)
domino.cpp: In function 'int main()':
domino.cpp:46:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, std::pair<std::pair<int, int>, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | if(sd.size() < (k - 1) * 7 + 1){
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~
domino.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, std::pair<std::pair<int, int>, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | if(sd.size() < (k - 1) * 7 + 1){
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~
# | 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... |