oj.uz

Submission #242591

# Submission time Handle Problem Language Result Execution time Memory
242591 2020-06-28T10:18:45 Z valerikk T-Covering (eJOI19_covering) C++17
15 / 100
 103 ms 16248 KB 
#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] == -1)
            {
                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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 892 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 103 ms 16248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 32 ms 5216 KB Output is correct
5 Correct 95 ms 16248 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Incorrect 7 ms 892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 892 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 103 ms 16248 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 15 ms 1920 KB Output is correct
9 Correct 32 ms 5216 KB Output is correct
10 Correct 95 ms 16248 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Incorrect 7 ms 892 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 8 ms 892 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 34 ms 5112 KB Output is correct
5 Correct 103 ms 16248 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 15 ms 1920 KB Output is correct
9 Correct 32 ms 5216 KB Output is correct
10 Correct 95 ms 16248 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Incorrect 7 ms 892 KB Output isn't correct
13 Halted 0 ms 0 KB -