Submission #1221568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221568		Aisha	T-Covering (eJOI19_covering)	C++20	10 / 100	118 ms	16168 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 + 1, vector <int> (m + 1));

    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 < 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;
    }

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

    return 0;
}

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