Submission #464404

#	Time	Username	Problem	Language	Result	Execution time	Memory
464404		tengiz05	T-Covering (eJOI19_covering)	C++17	100 / 100	139 ms	20072 KiB

covering

#include <bits/stdc++.h>

using i64 = long long;

std::vector<std::pair<int, int>> dir{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void ohNo() {
    std::cout << "No\n";
    exit(0);
}

struct Component {
    int sum, size;
    int have, mn;
    Component() : sum(0), size(0), have(0), mn(1e9) {}
    void add_adj(int x) {
        sum += x;
        have++;
        mn = std::min(mn, x);
    }
    int ans() {
        if (size * 3 > have) {
            ohNo();
        }
        return sum - (have - size * 3) * mn;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector a(n + 2, std::vector<int>(m + 2));
    std::vector vis(n + 2, std::vector<int>(m + 2, 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> a[i][j];
            vis[i][j] = 0;
        }
    }
    
    int k;
    std::cin >> k;
    std::vector<int> r(k), c(k);
    std::vector<bool> bad(k);
    std::vector red(n + 2, std::vector<int>(m + 2, -1));
    for (int i = 0; i < k; i++) {
        std::cin >> r[i] >> c[i];
        r[i]++;
        c[i]++;
        red[r[i]][c[i]] = i;
        vis[r[i]][c[i]]++;
    }
    
    for (int i = 0; i < k; i++) {
        int x = r[i], y = c[i];
        if (~red[x][y + 1]) {
            bad[red[x][y + 1]] = bad[i] = true;
            vis[x][y - 1]++;
            vis[x][y + 2]++;
            vis[x - 1][y]++;
            vis[x + 1][y]++;
            vis[x - 1][y + 1]++;
            vis[x + 1][y + 1]++;
        }
        if (~red[x + 1][y + 1]) {
            bad[red[x + 1][y + 1]] = bad[i] = true;
            vis[x - 1][y]++;
            vis[x][y - 1]++;
            vis[x + 1][y]++;
            vis[x][y + 1]++;
            if (x + 2 > n || y + 2 > m) ohNo();
            vis[x + 1][y + 2]++;
            vis[x + 2][y + 1]++;
        }
        if (~red[x - 1][y + 1]) {
            bad[red[x - 1][y + 1]] = bad[i] = true;
            vis[x][y - 1]++;
            vis[x + 1][y]++;
            vis[x - 1][y]++;
            vis[x][y + 1]++;
            if (y + 2 > m || x - 2 < 1) ohNo();
            vis[x - 1][y + 2]++;
            vis[x - 2][y + 1]++;
        }
    }
    
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            if (vis[i][j] > 1) {
                ohNo();
            }
        }
    }
    
    std::vector counted(n + 2, std::vector<bool>(m + 2, true));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            counted[i][j] = vis[i][j];
        }
    }
    
    std::vector<Component> comp;
    for (int i = 0; i < k; i++) {
        if (bad[i]) continue;
        std::queue<std::pair<int, int>> que;
        que.emplace(r[i], c[i]);
        Component nw;
        bad[i] = true;
        while (!que.empty()) {
            auto [x, y] = que.front();
            que.pop();
            nw.size++;
            for (auto [dx, dy] : dir) {
                int nx = x + dx, ny = y + dy;
                if (!counted[nx][ny]) {
                    counted[nx][ny] = true;
                    nw.add_adj(a[nx][ny]);
                }
            }
            for (auto [dx, dy] : dir) {
                int nx = x + dx * 2, ny = y + dy * 2;
                if (nx < 0 || ny < 0 || nx > n || ny > m) continue;
                if (~red[nx][ny] && !bad[red[nx][ny]]) {
                    bad[red[nx][ny]] = true;
                    que.emplace(nx, ny);
                }
            }
        }
        comp.push_back(nw);
    }
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans += a[i][j] * vis[i][j];
        }
    }
    
    for (auto x : comp) {
        ans += x.ans();
    }
    
    std::cout << ans << "\n";
    
    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