#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, k;
bool out( int i, int j ) {
return i < 1 || i > n || j < 1 || j > m;
}
int dx[12] = { -1, 0, 1, 0, 1, -1, -1, 1, -2, 0, 2, 0 };
int dy[12] = { 0, -1, 0, 1, 1, 1, -1, -1, 0, -2, 0, 2 };
int dxv[4] = { -1, 0, 1, 0 };
int dyv[4] = { 0, 1, 0, -1 };
vector<pair<int, int>> cell;
vector<int> winn;
vector<vector<int>> viz;
vector<vector<int>> w, t;
void dfs( int x, int y ) {
cell.push_back({ x, y });
viz[x][y] = 1;
for ( int dir = 0; dir < 12; ++dir ) {
int nx = x + dx[dir], ny = y + dy[dir];
if ( !out( nx, ny ) && !viz[nx][ny] && t[nx][ny] ) {
dfs( x + dx[dir], y + dy[dir] );
}
}
}
int maxWin() {
int ngh = 0;
int s = 0;
for ( int i = 0; i < cell.size(); ++i ) {
viz[cell[i].first][cell[i].second] = 2;
++ngh;
s += w[cell[i].first][cell[i].second];
for ( int d = 0; d < 4; ++d ) {
int nx = cell[i].first + dxv[d];
int ny = cell[i].second + dyv[d];
if ( !out( nx, ny ) && !t[nx][ny] && viz[nx][ny] != 2 ) {
++ngh;
s += w[nx][ny];
winn.push_back( w[nx][ny] );
viz[nx][ny] = 2;
}
}
}
sort( winn.begin(), winn.end() );
reverse( winn.begin(), winn.end() );
if ( 4 * cell.size() > ngh ) {
return -1;
}
int diff = ngh - 4 * cell.size();
while ( diff-- ) {
s -= winn.back();
winn.pop_back();
}
winn.clear();
return s;
}
int main() {
cin >> n >> m;
int x;
vector<int> a, b, c;
for ( int i = 1; i <= m; ++i ) {
a.push_back( 0 );
b.push_back( 0 );
c.push_back( 1 );
}
w.push_back( a );
t.push_back( b );
viz.push_back( c );
for ( int i = 1; i <= n; ++i ) {
a.clear();
b.clear();
c.clear();
a.push_back( 0 );
b.push_back( 0 );
c.push_back( 1 );
for ( int j = 1; j <= m; ++j ) {
cin >> x;
a.push_back( x );
b.push_back( 0 );
c.push_back( 0 );
}
w.push_back( a );
t.push_back( b );
viz.push_back( c );
}
cin >> k;
for ( int i = 0; i < k; ++i ) {
int x, y;
cin >> x >> y;
t[x + 1][y + 1] = 1;
}
int res = 0;
bool ok = true;
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
if ( !viz[i][j] && t[i][j] == 1 ) {
dfs( i, j );
x = maxWin();
if ( x == -1 ) {
ok = false;
}
res += x;
cell.clear();
}
}
}
if ( ok ) {
cout << res;
} else {
cout << "No";
}
return 0;
}
Compilation message
covering.cpp: In function 'int maxWin()':
covering.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for ( int i = 0; i < cell.size(); ++i ) {
| ~~^~~~~~~~~~~~~
covering.cpp:56:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
56 | if ( 4 * cell.size() > ngh ) {
| ~~~~~~~~~~~~~~~~^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
716 KB |
Output is correct |
3 |
Correct |
26 ms |
1884 KB |
Output is correct |
4 |
Correct |
82 ms |
5064 KB |
Output is correct |
5 |
Correct |
256 ms |
15948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
704 KB |
Output is correct |
3 |
Correct |
26 ms |
1860 KB |
Output is correct |
4 |
Correct |
80 ms |
5016 KB |
Output is correct |
5 |
Correct |
260 ms |
15908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
436 KB |
Output is correct |
2 |
Correct |
8 ms |
740 KB |
Output is correct |
3 |
Correct |
26 ms |
1796 KB |
Output is correct |
4 |
Correct |
78 ms |
5024 KB |
Output is correct |
5 |
Correct |
260 ms |
15992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
14 ms |
1192 KB |
Output is correct |
4 |
Correct |
10 ms |
844 KB |
Output is correct |
5 |
Correct |
28 ms |
2060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
716 KB |
Output is correct |
3 |
Correct |
26 ms |
1884 KB |
Output is correct |
4 |
Correct |
82 ms |
5064 KB |
Output is correct |
5 |
Correct |
256 ms |
15948 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
8 ms |
704 KB |
Output is correct |
8 |
Correct |
26 ms |
1860 KB |
Output is correct |
9 |
Correct |
80 ms |
5016 KB |
Output is correct |
10 |
Correct |
260 ms |
15908 KB |
Output is correct |
11 |
Correct |
3 ms |
436 KB |
Output is correct |
12 |
Correct |
8 ms |
740 KB |
Output is correct |
13 |
Correct |
26 ms |
1796 KB |
Output is correct |
14 |
Correct |
78 ms |
5024 KB |
Output is correct |
15 |
Correct |
260 ms |
15992 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
14 ms |
1192 KB |
Output is correct |
19 |
Correct |
10 ms |
844 KB |
Output is correct |
20 |
Correct |
28 ms |
2060 KB |
Output is correct |
21 |
Correct |
3 ms |
460 KB |
Output is correct |
22 |
Correct |
9 ms |
712 KB |
Output is correct |
23 |
Correct |
31 ms |
1772 KB |
Output is correct |
24 |
Correct |
89 ms |
5004 KB |
Output is correct |
25 |
Correct |
257 ms |
16012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
716 KB |
Output is correct |
3 |
Correct |
26 ms |
1884 KB |
Output is correct |
4 |
Correct |
82 ms |
5064 KB |
Output is correct |
5 |
Correct |
256 ms |
15948 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
8 ms |
704 KB |
Output is correct |
8 |
Correct |
26 ms |
1860 KB |
Output is correct |
9 |
Correct |
80 ms |
5016 KB |
Output is correct |
10 |
Correct |
260 ms |
15908 KB |
Output is correct |
11 |
Correct |
3 ms |
436 KB |
Output is correct |
12 |
Correct |
8 ms |
740 KB |
Output is correct |
13 |
Correct |
26 ms |
1796 KB |
Output is correct |
14 |
Correct |
78 ms |
5024 KB |
Output is correct |
15 |
Correct |
260 ms |
15992 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
14 ms |
1192 KB |
Output is correct |
19 |
Correct |
10 ms |
844 KB |
Output is correct |
20 |
Correct |
28 ms |
2060 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
9 ms |
712 KB |
Output is correct |
28 |
Correct |
31 ms |
1772 KB |
Output is correct |
29 |
Correct |
89 ms |
5004 KB |
Output is correct |
30 |
Correct |
257 ms |
16012 KB |
Output is correct |
31 |
Correct |
366 ms |
22164 KB |
Output is correct |
32 |
Correct |
265 ms |
16316 KB |
Output is correct |
33 |
Correct |
272 ms |
18636 KB |
Output is correct |
34 |
Correct |
267 ms |
16448 KB |
Output is correct |
35 |
Correct |
312 ms |
21064 KB |
Output is correct |