Submission #1096991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096991		raphaelp	Game (eJOI20_game)	C++14	100 / 100	1 ms	600 KiB

game

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20