oj.uz

Submission #919318

# Submission time Handle Problem Language Result Execution time Memory
919318 2024-01-31T15:06:16 Z raphaelp T-Covering (eJOI19_covering) C++14
0 / 100
 47 ms 6236 KB 
#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)
{
    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 (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;
    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 (special[x + depX[j]][y + depY[j]] == 1)
            place(x + depX[j], y + depY[j], special, p, depX, depY, N, M, tot, Tab, minn);
        if (special[x + depX[j - 8]][y + depY[j - 8]] == 3)
        {
            tot -= Tab[x + depX[j - 8]][y + depY[j - 8]];
            for (long long k = 0; k < 4; k++)
                special[x + depX[k]][y + depY[k]] = 3;
            return;
        }
    }
    if (choose == -1)
        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);
        if (p == 0)
            break;
    }
    if (p)
        cout << tot;
    else
        cout << "No";
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 5 ms 1116 KB Output is correct
3 Runtime error 18 ms 4024 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 15 ms 2552 KB Output is correct
4 Incorrect 47 ms 6236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 30.0

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