Submission #464376

#	Time	Username	Problem	Language	Result	Execution time	Memory
464376		tengiz05	T-Covering (eJOI19_covering)	C++17	25 / 100	101 ms	15880 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);
}

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++) {
    //         std::cout << vis[i][j] << " ";
    //     }std::cout << "\n";
    // }
    
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            if (vis[i][j] > 1) {
                ohNo();
            }
        }
    }
    
    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 (int i = 0; i < k; i++) {
        if (bad[i]) continue;
        int res = 0, cnt = 0;
        int x = r[i], y = c[i];
        for (auto [dx, dy] : dir) {
            cnt += vis[x + dx][y + dy];
            res += a[x + dx][y + dy];
        }
        if (cnt > 1) {
            ohNo();
        }
        int v = 0;
        for (auto [dx, dy] : dir) {
            if (cnt == 0 || vis[x + dx][y + dy]) {
                v = std::max(v, res - a[x + dx][y + dy]);
            }
        }
        ans += v;
    }
    
    std::cout << ans << "\n";
    
    return 0;
}

• 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