제출 #1221575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221575		Aisha	T-Covering (eJOI19_covering)	C++20	100 / 100	164 ms	26868 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    int n, m;
    cin >> n >> m;

    vector <vector <int>> a(n + 1, vector <int> (m + 1));
    vector <vector <int>> vis(n + 2, vector <int> (m + 2));

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }
    
    int ans = 0;
    bool ok = true;

    int k;
    cin >> k;

    vector <pair <int, int>> v(k);
    for (int i = 0; i < k; i ++) cin >> v[i].first >> v[i].second;
    for (int i = 0; i < k; i ++) vis[++ v[i].first][++ v[i].second] = -1;

    int k1 = 0, sum = 0, cnt = 0, mn = 1e18;
    vector <int> dx = {-1, 0, 0, 1, -1, -1, 1, 1};
    vector <int> dy = {0, -1, 1, 0, -1, 1, -1, 1};

    auto dfs = [&](auto&& dfs, int x, int y) -> void {
        if (x <= 0 || y <= 0 || x > n || y > m || vis[x][y] == 1) return;
        if (vis[x][y] == 0) {
            cnt ++;
            sum += a[x][y];
            mn = min(mn, a[x][y]);
        } else {
            k1 ++;
            sum += a[x][y];
        }

        // cout << x << ' ' << y << endl;
        // cout << k1 << ' ' << sum << ' ' << cnt << ' ' << mn << endl;

        if (vis[x][y] == -1) {
            vis[x][y] = 1;
            for (int i = 0; i < 4; i ++) dfs(dfs, x + dx[i], y + dy[i]);
            for (int i = 4; i < 8; i ++) {
                if (vis[x + dx[i]][y + dy[i]] == -1) {
                    dfs(dfs, x + dx[i], y + dy[i]);
                }
            }
        } else {
            vis[x][y] = 1;
            for (int i = 0; i < 4; i ++) {
                if (vis[x + dx[i]][y + dy[i]] == -1) {
                    dfs(dfs, x + dx[i], y + dy[i]);
                }
            }
        }
    };

    for (int i = 0; i < k; i ++) {
        int x = v[i].first;
        int y = v[i].second;

        if (vis[x][y] == 1) continue;
        k1 = sum = cnt = 0; mn = 1e18;
        dfs(dfs, x, y);
       // cout << k1 << ' ' << sum << ' ' << cnt << ' ' << mn << endl;
        
        if (cnt < k1 * 3) ok = false;
        else if (cnt == k1 * 3) ans += sum;
        else ans += sum - mn;

       // cout << ok << endl;
    }

    if (!ok) cout << "No" << endl;
    else cout << ans << endl;

    return 0;
}

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