제출 #242585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242585		valerikk	T-Covering (eJOI19_covering)	C++17	0 / 100	6 ms	512 KiB

covering

#include<bits/stdc++.h>
using namespace std;

const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, 1, 0, -1};
const int INF = 1e9 + 5;

int n, m;

bool check(int i, int j)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> a[i][j];
        }
    }
    vector<vector<bool>> used(n, vector<bool>(m, 0));
    int k;
    cin >> k;
    for (int _ = 0; _ < k; ++_)
    {
        int r, c;
        cin >> r >> c;
        used[r][c] = 1;
    }
    vector<vector<int>> go(n, vector<int>(m, -1));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (used[i][j])
            {
                for (int h = 0; h < 4; ++h)
                {
                    int x = i + DX[h], y = j + DY[h];
                    if (check(x, y) && used[x][y])
                    {
                        go[i][j] = h;
                        go[x][y] = h ^ 2;
                    }
                }
            }
        }
    }
    vector<vector<int>> cnt(n, vector<int>(m, 0));
    long long ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (!used[i][j])
            {
                continue;
            }
            if (~go[i][j])
            {
                int mx = -INF;
                for (int h = 0; h < 4; ++h)
                {
                    int sum = a[i][j];
                    bool fl = 1;
                    for (int h2 = 0; h2 < 4; ++h2)
                    {
                        if (h2 != h)
                        {
                            int x = i + DX[h2], y = j + DY[h2];
                            if (!check(x, y))
                            {
                                fl = 0;
                                break;
                            }
                            sum += a[x][y];
                        }
                    }
                    if (fl)
                    {
                        mx = max(mx, sum);
                    }
                }
                if (mx == -INF)
                {
                    cout << "No\n";
                    return 0;
                }
                ans += mx;
            }
            else
            {
                bool fl = 1;
                int sum = a[i][j];
                ++cnt[i][j];
                for (int h = 0; h < 4; ++h)
                {
                    if (h != go[i][j])
                    {
                        int x = i + DX[h], y = j + DY[h];
                        if (!check(x, y))
                        {
                            fl = 0;
                            break;
                        }
                        sum += a[x][y];
                        ++cnt[x][y];
                    }
                }
                if (!fl)
                {
                    cout << "No\n";
                    return 0;
                }
                ans += sum;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (cnt[i][j] >= 2)
            {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << ans;
    return 0;
}

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