Submission #1312713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312713		penguin133	T-Covering (eJOI19_covering)	C++20	25 / 100	159 ms	23920 KiB

covering

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dy[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};

void die(){
    cout << "No";
    exit(0);
}

int main() {
	int n, m; cin >> n >> m;
    ll a[n + 1][m + 1], b[n + 1][m + 1] = {0}, vis[n + 1][m + 1] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    int k; cin >> k;
    while (k--) {
        int x, y; cin >> x >> y;
        x++; y++;
        if (b[x][y]) {
            cout << "No";
            return 0;
        }
        b[x][y] = 1;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!b[i][j]) continue;
            ans += a[i][j];
            int c = 0;
            for (int aa = 0; aa < 8; aa++) {
                int x1 = i + dx[aa], y1 = j + dy[aa];
                if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
                if (b[x1][y1]) c++;
            }
            if (c >= 2) {
                cout << "No";
                return 0;
            }
            if (c) {
                for (int aa = 0; aa < 8; aa++) {
                    int x1 = i + dx[aa], y1 = j + dy[aa];
                    if (x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;
                    if (b[x1][y1]) {
                        if (aa <= 1 || aa == 7) {
                            if (j == 1 || j == m || i == n) die();
                            ans += a[i][j - 1] + a[i][j + 1] + a[i + 1][j];
                        }
                        else if (aa == 2) {
                            if (j == 1 || i == 1 || i == n) die();
                            ans += a[i - 1][j] + a[i][j - 1] + a[i + 1][j];
                        }
                        else if (aa >= 3 && aa <= 5) {
                            if (i == 1 || j == 1 || j == m) die();
                            ans += a[i - 1][j] + a[i][j - 1] + a[i][j + 1];
                        }
                        else {
                            if (i == n || i == 1 || j == m) die();
                            ans += a[i - 1][j] + a[i + 1][j] + a[i][j + 1];
                        }
                    }
                }
            }
            else {
                if ((i == 1 || i == n) && (j == 1 || j == m)) die();
                if (i == 1) ans += a[i][j - 1] + a[i][j + 1] + a[i + 1][j];
                else if (i == n) ans += a[i][j - 1] + a[i][j + 1] + a[i - 1][j];
                else if (j == 1) ans += a[i][j + 1] + a[i + 1][j] + a[i - 1][j];
                else if (j == m) ans += a[i][j - 1] + a[i + 1][j] + a[i - 1][j];
                else ans += a[i][j - 1] + a[i][j + 1] + a[i - 1][j] + a[i + 1][j] - min({a[i - 1][j], a[i + 1][j], a[i][j - 1], a[i][j + 1]});
            }
        }
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30