#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define REP(i,a) for (int i = 0; i < (a); i++)
#define add push_back
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
//const ll MOD = 1000000007LL;
const ll MOD = 998244353LL;
int ni() {
int x; cin >> x;
return x;
}
ll nl() {
ll x; cin >> x;
return x;
}
double nd() {
double x; cin >> x;
return x;
}
string next() {
string x; cin >> x;
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<vi> dirs;
vector<vi> dirs1;
for (int x = -2; x <= 2; x++) {
for (int y = -2; y <= 2; y++) {
int d = abs(x)+abs(y);
if (0<d&&d<=2) {
vi dir = {x,y};
dirs.add(dir);
}
if (0<d&&d<=1) {
vi dir = {x,y};
dirs1.add(dir);
}
}
}
int ans = 0;
const int N = ni();
const int M = ni();
int grid[N][M];
int occ[N][M];
REP(i,N) REP(j,M) {
grid[i][j] = ni();
occ[i][j] = 0;
}
const int K = ni();
vector<pii> points(K);
REP(i,K) {
int r = ni();
int c = ni();
occ[r][c] = i+1;
points[i] = {r,c};
}
int vis[K+1];
for(int i = 0;i <= K;i++)
vis[i] = 0;
for (int i = 1; i <= K; i++) {
if (vis[i]) continue;
vis[i] = 1;
queue<pii> q;
q.push(points[i-1]);
vector<pii> center;
set<pii> slots;
int cnt = 0;
while (!q.empty()) {
pii point = q.front();
q.pop();
cnt += 3;
center.add(point);
for (auto dir: dirs) {
int newR = point.first+dir[0];
int newC = point.second+dir[1];
if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
int g = occ[newR][newC];
if (g > 0 && !vis[g]) {
vis[g] = 1;
q.push({newR,newC});
}
}
}
}
for (pii point: center) {
for (auto dir: dirs1) {
int newR = point.first+dir[0];
int newC = point.second+dir[1];
if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
int g = occ[newR][newC];
if (g == 0) {
slots.insert({newR,newC});
}
}
}
}
if (sz(slots) < cnt) {
cout << "No\n";
return 0;
}
vi gain;
for (pii slot: slots) {
gain.add(grid[slot.first][slot.second]);
}
sort(gain.begin(),gain.end(),greater<int>());
for (int j = 0; j < cnt; j++)
ans += gain[j];
for (pii point: center) {
ans += grid[point.first][point.second];
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
9 ms |
1092 KB |
Output is correct |
4 |
Correct |
28 ms |
2660 KB |
Output is correct |
5 |
Correct |
91 ms |
8132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
12 ms |
1088 KB |
Output is correct |
4 |
Correct |
30 ms |
2636 KB |
Output is correct |
5 |
Correct |
93 ms |
8116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
9 ms |
972 KB |
Output is correct |
4 |
Correct |
29 ms |
2644 KB |
Output is correct |
5 |
Correct |
104 ms |
8124 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 |
5 ms |
588 KB |
Output is correct |
4 |
Correct |
5 ms |
460 KB |
Output is correct |
5 |
Correct |
10 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 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 |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
9 ms |
1092 KB |
Output is correct |
4 |
Correct |
28 ms |
2660 KB |
Output is correct |
5 |
Correct |
91 ms |
8132 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
460 KB |
Output is correct |
8 |
Correct |
12 ms |
1088 KB |
Output is correct |
9 |
Correct |
30 ms |
2636 KB |
Output is correct |
10 |
Correct |
93 ms |
8116 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
460 KB |
Output is correct |
13 |
Correct |
9 ms |
972 KB |
Output is correct |
14 |
Correct |
29 ms |
2644 KB |
Output is correct |
15 |
Correct |
104 ms |
8124 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
5 ms |
588 KB |
Output is correct |
19 |
Correct |
5 ms |
460 KB |
Output is correct |
20 |
Correct |
10 ms |
1108 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
460 KB |
Output is correct |
23 |
Correct |
10 ms |
1092 KB |
Output is correct |
24 |
Correct |
28 ms |
2636 KB |
Output is correct |
25 |
Correct |
92 ms |
8116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
9 ms |
1092 KB |
Output is correct |
4 |
Correct |
28 ms |
2660 KB |
Output is correct |
5 |
Correct |
91 ms |
8132 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
460 KB |
Output is correct |
8 |
Correct |
12 ms |
1088 KB |
Output is correct |
9 |
Correct |
30 ms |
2636 KB |
Output is correct |
10 |
Correct |
93 ms |
8116 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
460 KB |
Output is correct |
13 |
Correct |
9 ms |
972 KB |
Output is correct |
14 |
Correct |
29 ms |
2644 KB |
Output is correct |
15 |
Correct |
104 ms |
8124 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
5 ms |
588 KB |
Output is correct |
19 |
Correct |
5 ms |
460 KB |
Output is correct |
20 |
Correct |
10 ms |
1108 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
460 KB |
Output is correct |
28 |
Correct |
10 ms |
1092 KB |
Output is correct |
29 |
Correct |
28 ms |
2636 KB |
Output is correct |
30 |
Correct |
92 ms |
8116 KB |
Output is correct |
31 |
Correct |
410 ms |
18596 KB |
Output is correct |
32 |
Correct |
97 ms |
8860 KB |
Output is correct |
33 |
Correct |
103 ms |
9756 KB |
Output is correct |
34 |
Correct |
100 ms |
9028 KB |
Output is correct |
35 |
Correct |
217 ms |
17344 KB |
Output is correct |