Submission #919342

#	Time	Username	Problem	Language	Result	Execution time	Memory
919342		raphaelp	T-Covering (eJOI19_covering)	C++14	100 / 100	234 ms	32532 KiB

covering

#include <bits/stdc++.h>
using namespace std;
void place(long long x, long long y, vector<vector<long long>> &special, long long &p, vector<long long> &depX, vector<long long> &depY, long long N, long long M, long long &tot, vector<vector<long long>> &Tab, long long &minn, int px, int py)
{
    if (special[x][y] == 2)
        return;
    if (special[x][y] == 3)
    {
        p = 0;
        return;
    }
    tot += Tab[x][y];
    long long choose = -1;
    for (long long j = 0; j < 4; j++)
    {
        if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
        {
            if (choose != -1)
                p = 0;
            choose = j;
        }
        else
        {
            minn = min(minn, Tab[x + depX[j]][y + depY[j]]);
            tot += Tab[x + depX[j]][y + depY[j]];
            if (special[x + depX[j]][y + depY[j]] > 0)
            {
                if (choose != -1)
                    p = 0;
                choose = j;
            }
        }
    }
    for (long long j = 4; j < 8; j++)
    {
        if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
            continue;
        if (special[x + depX[j]][y + depY[j]] == 1)
        {
            if (choose != -1)
                p = 0;
            choose = j - 4;
        }
    }
    if (p == 0)
        return;
    for (long long j = 0; j < 4; j++)
    {
        if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
            continue;
        if (j == choose)
        {
            tot -= Tab[x + depX[j]][y + depY[j]];
        }
        else if (choose != -1)
            special[x + depX[j]][y + depY[j]] = 3;
    }

    special[x][y] = 2;
    if (choose != -1)
        return;
    special[x][y] = 4;
    for (long long j = 8; j < 12; j++)
    {
        if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
            continue;
        if (x + depX[j] == px && y + depY[j] == py)
            continue;
        if (special[x + depX[j]][y + depY[j]] == 1)
        {
            place(x + depX[j], y + depY[j], special, p, depX, depY, N, M, tot, Tab, minn, x, y);
            tot -= Tab[x + depX[j - 8]][y + depY[j - 8]];
        }
        if (special[x + depX[j]][y + depY[j]] == 4)
        {
            tot -= Tab[x + depX[j - 8]][y + depY[j - 8]];
            for (long long k = 0; k < 4; k++)
            {
                if (x + depX[k] < 0 || x + depX[k] >= N || y + depY[k] < 0 || y + depY[k] >= M)
                    continue;
                if (k != j - 8)
                    special[x + depX[k]][y + depY[k]] = 3;
            }
        }
        if (special[x + depX[j - 8]][y + depY[j - 8]] == 3)
        {
            for (long long k = 0; k < 4; k++)
            {
                if (x + depX[k] < 0 || x + depX[k] >= N || y + depY[k] < 0 || y + depY[k] >= M)
                    continue;
                special[x + depX[k]][y + depY[k]] = 3;
            }
            special[x][y] = 2;
            return;
        }
    }
    special[x][y] = 2;
    if (choose == -1 && x == px && y == py)
        tot -= minn;
}
int main()
{
    long long N, M;
    cin >> N >> M;
    vector<vector<long long>> Tab(N, vector<long long>(M));
    for (long long i = 0; i < N; i++)
    {
        for (long long j = 0; j < M; j++)
        {
            cin >> Tab[i][j];
        }
    }
    long long K;
    cin >> K;
    vector<vector<long long>> special(N, vector<long long>(M));
    vector<pair<long long, long long>> S;
    for (long long i = 0; i < K; i++)
    {
        long long a, b;
        cin >> a >> b;
        S.push_back({a, b});
        special[a][b] = 1;
    }
    long long p = 1, tot = 0;
    vector<long long> depX = {0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2}, depY = {-1, 0, 1, 0, -1, 1, 1, -1, -2, 0, 2, 0};
    for (long long i = 0; i < K; i++)
    {
        long long x = S[i].first;
        long long y = S[i].second;
        long long minn = 1000000;
        place(x, y, special, p, depX, depY, N, M, tot, Tab, minn, x, y);
        if (p == 0)
            break;
    }
    if (p)
        cout << tot;
    else
        cout << "No";
}

• 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