| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 242383 | valerikk | T-Covering (eJOI19_covering) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll oo = 2e18;
int n, m;
int **a;
bool **f;
short **d;
int **c;
bool ok(int i, int j) {
return i >= 0 && i < n && j >= 0 && j < m;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
a = new ll*[n];
f = new bool*[n];
d = new int*[n];
c = new int*[n];
for (int i = 0; i < n; ++i) {
a[i] = new ll[m];
f[i] = new bool[m];
d[i] = new int[m];
c[i] = new int[m];
for (int j = 0; j < m; ++j) cin >> a[i][j];
}
memset(d, 255, sizeof(d));
int k;
cin >> k;
while (k--) {
int r, c;
cin >> r >> c;
f[r][c] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!f[i][j]) continue;
for (int z = 0; z < 4; ++z) {
int x = i + dx[z], y = j + dy[z];
if (ok(x, y) && f[x][y]) {
d[i][j] = z;
d[x][y] = z ^ 2;
}
}
}
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (f[i][j]) {
if (~d[i][j]) {
ll mx = -oo;
for (int z = 0; z < 4; ++z) {
bool OK = 1;
for (int zz = 0; zz < 4; ++zz) {
if (zz != z) OK &= ok(i + dx[zz], j + dy[zz]);
}
if (OK) {
ll q = a[i][j];
for (int zz = 0; zz < 4; ++zz) {
if (zz != z) q += a[i + dx[zz]][j + dy[zz]];
}
mx = max(mx, q);
}
}
ans += mx;
} else {
bool OK = 1;
for (int z = 0; z < 4; ++z) {
if (d[i][j] != z) OK &= ok(i + dx[z], j + dy[z]);
}
if (!OK) {
cout << "No\n";
return 0;
}
ll q = 0;
for (int z = 0; z < 4; ++z) {
if (d[i][j] != z) {
q += a[i + dx[z]][j + dy[z]];
++c[i + dx[z]][j + dy[z]];
}
}
ans += q;
}
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (c[i][j] > 1) {
cout << "No\n";
return 0;
}
}
}
cout << ans;
return 0;
}