oj.uz

Submission #1096991

# Submission time Handle Problem Language Result Execution time Memory
1096991 2024-10-05T16:19:33 Z raphaelp Game (eJOI20_game) C++14
100 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
int dfs(pair<int, int> init, pair<int, int> p, int x, int y, vector<string> &H, vector<string> &V, vector<vector<int>> &occ, int N, int M, vector<int> &ones, vector<int> &fours, vector<int> &eights)
{
    occ[x][y] = 1;
    int tot = 1;
    if ((x > 0 && occ[x - 1][y] && H[x][y] == '0' && !(p.first == x - 1 && p.second == y)) || (x < N - 1 && occ[x + 1][y] && H[x + 1][y] == '0' && !(p.first == x + 1 && p.second == y)) || (y > 0 && occ[x][y - 1] && V[x][y] == '0' && !(p.first == x && p.second == y - 1)) || (y < M - 1 && occ[x][y + 1] && V[x][y + 1] == '0' && !(p.first == x && p.second == y + 1)))
        return -1;
    if (x > 0 && H[x][y] == '0' && !occ[x - 1][y])
        tot += dfs(init, {x, y}, x - 1, y, H, V, occ, N, M, ones, fours, eights);
    if (x < N - 1 && H[x + 1][y] == '0' && !occ[x + 1][y])
        tot += dfs(init, {x, y}, x + 1, y, H, V, occ, N, M, ones, fours, eights);
    if (y > 0 && V[x][y] == '0' && !occ[x][y - 1])
        tot += dfs(init, {x, y}, x, y - 1, H, V, occ, N, M, ones, fours, eights);
    if (y < M - 1 && V[x][y + 1] == '0' && !occ[x][y + 1])
        tot += dfs(init, {x, y}, x, y + 1, H, V, occ, N, M, ones, fours, eights);
    if ((tot == 1 || tot == 2) && init.first == x && init.second == y)
    {
        if (H[x][y] == '1' && H[x + 1][y] == '1' && V[x][y] == '1' && V[x][y + 1] == '1')
            tot = 0;
        else
            ones.push_back(-tot);
        return 0;
    }
    if (init.first == x && init.second == y)
    {
        if (tot < 1)
            eights.push_back(tot - 2);
        else
            fours.push_back(-tot);
    }
    if (tot < 1)
        return tot - 2;
    return tot;
}
int main()
{
    int N, M;
    cin >> N >> M;
    vector<string> V(M + 1), H(N + 1);
    for (int i = 0; i <= N; i++)
        cin >> H[i];
    for (int i = 0; i < N; i++)
        cin >> V[i];
    vector<vector<int>> occ(N, vector<int>(M));
    vector<int> fours, ones, eights;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (occ[i][j])
                continue;
            int temp = dfs({i, j}, {i, j}, i, j, H, V, occ, N, M, ones, fours, eights);
        }
    }
    sort(ones.begin(), ones.end());
    for (int i = 0; i < ones.size() / 2; i++)
        swap(ones[i], ones[ones.size() - i - 1]);
    sort(fours.begin(), fours.end());
    for (int i = 0; i < fours.size() / 2; i++)
        swap(fours[i], fours[fours.size() - i - 1]);
    sort(eights.begin(), eights.end());
    for (int i = 0; i < eights.size() / 2; i++)
        swap(eights[i], eights[eights.size() - i - 1]);
    vector<vector<vector<vector<int>>>> dp(2, vector<vector<vector<int>>>(ones.size() + 1, vector<vector<int>>(fours.size() + 1, vector<int>(eights.size() + 1, 123456789))));
    dp[0][ones.size()][fours.size()][eights.size()] = 0;
    dp[1][ones.size()][fours.size()][eights.size()] = 0;
    for (int j = ones.size(); j >= 0; j--)
    {
        for (int k = fours.size(); k >= 0; k--)
        {
            for (int l = eights.size(); l >= 0; l--)
            {
                int dp1jk1l = 123456789, dp0jk1l = 123456789, dp1jkl1 = 123456789, dp0jkl1 = 123456789;
                if (dp[0][j][k][l] != 123456789)
                {
                    if (j > 0)
                    {
                        if (dp[1][j - 1][k][l] == 123456789)
                            dp[1][j - 1][k][l] = dp[0][j][k][l] - ones[j - 1];
                        dp[1][j - 1][k][l] = min(dp[1][j - 1][k][l], dp[0][j][k][l] - ones[j - 1]);
                    }
                    if (k > 0)
                    {
                        if (dp1jk1l == 123456789)
                            dp1jk1l = dp[0][j][k][l] - fours[k - 1];
                        dp1jk1l = max(dp1jk1l, dp[0][j][k][l] - fours[k - 1]);
                        if (dp0jk1l == 123456789)
                            dp0jk1l = dp[0][j][k][l] + fours[k - 1] + 4;
                        dp0jk1l = min(dp[0][j][k - 1][l], dp[0][j][k][l] + fours[k - 1] + 4);
                    }
                    if (l > 0)
                    {
                        if (dp1jkl1 == 123456789)
                            dp1jkl1 = dp[0][j][k][l] - eights[l - 1];
                        dp1jkl1 = max(dp1jkl1, dp[0][j][k][l] - eights[l - 1]);
                        if (dp0jkl1 == 123456789)
                            dp0jkl1 = dp[0][j][k][l] + eights[l - 1] + 8;
                        dp0jkl1 = min(dp0jkl1, dp[0][j][k][l] + eights[l - 1] + 8);
                    }
                }
                if (dp[1][j][k][l] != 123456789)
                {
                    if (j > 0)
                    {
                        if (dp[0][j - 1][k][l] == 123456789)
                            dp[0][j - 1][k][l] = dp[1][j][k][l] + ones[j - 1];
                        dp[0][j - 1][k][l] = max(dp[0][j - 1][k][l], dp[1][j][k][l] + ones[j - 1]);
                    }
                    if (k > 0)
                    {
                        if (dp0jk1l == 123456789)
                            dp0jk1l = dp[1][j][k][l] + fours[k - 1];
                        dp0jk1l = min(dp0jk1l, dp[1][j][k][l] + fours[k - 1]);
                        if (dp1jk1l == 123456789)
                            dp1jk1l = dp[1][j][k][l] - fours[k - 1] - 4;
                        dp1jk1l = max(dp1jk1l, dp[1][j][k][l] - fours[k - 1] - 4);
                    }
                    if (l > 0)
                    {
                        if (dp0jkl1 == 123456789)
                            dp0jkl1 = dp[1][j][k][l] + eights[l - 1];
                        dp0jkl1 = min(dp0jkl1, dp[1][j][k][l] + eights[l - 1]);
                        if (dp1jkl1 == 123456789)
                            dp1jkl1 = dp[1][j][k][l] - eights[l - 1] - 8;
                        dp1jkl1 = max(dp1jkl1, dp[1][j][k][l] - eights[l - 1] - 8);
                    }
                }
                if (k > 0)
                {
                    if (dp[0][j][k - 1][l] == 123456789)
                        dp[0][j][k - 1][l] = dp0jk1l;
                    dp[0][j][k - 1][l] = max(dp[0][j][k - 1][l], dp0jk1l);
                    if (dp[1][j][k - 1][l] == 123456789)
                        dp[1][j][k - 1][l] = dp1jk1l;
                    dp[1][j][k - 1][l] = min(dp[1][j][k - 1][l], dp1jk1l);
                }
                if (l > 0)
                {
                    if (dp[0][j][k][l - 1] == 123456789)
                        dp[0][j][k][l - 1] = dp0jkl1;
                    dp[0][j][k][l - 1] = max(dp[0][j][k][l - 1], dp0jkl1);
                    if (dp[1][j][k][l - 1] == 123456789)
                        dp[1][j][k][l - 1] = dp1jkl1;
                    dp[1][j][k][l - 1] = min(dp[1][j][k][l - 1], dp1jkl1);
                }
            }
        }
    }
    cout << dp[0][0][0][0];
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:53:17: warning: unused variable 'temp' [-Wunused-variable]
   53 |             int temp = dfs({i, j}, {i, j}, i, j, H, V, occ, N, M, ones, fours, eights);
      |                 ^~~~
game.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < ones.size() / 2; i++)
      |                     ~~^~~~~~~~~~~~~~~~~
game.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < fours.size() / 2; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
game.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < eights.size() / 2; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 432 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 432 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 344 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 1 ms 600 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 1 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 1 ms 348 KB Output is correct
71 Correct 1 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 1 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 1 ms 348 KB Output is correct
78 Correct 0 ms 348 KB Output is correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 0 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Correct 1 ms 348 KB Output is correct