Submission #1212207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212207		badge881	Game (eJOI20_game)	C++20	100 / 100	4 ms	1092 KiB

game

#include "bits/stdc++.h"
using namespace std;

const int N = 25;
vector<int> edges[N * N], cycle, path;
int used[N * N], cntv, cnte;

map<array<int, 4>, int> mem;

int rec(int i, int j, int left, int t)
{
    if (i + 1 == (int)cycle.size() && j + 1 == (int)path.size())
        return left;
    if (mem.count({i, j, left, t}))
        return mem[{i, j, left, t}];
    int &res = mem[{i, j, left, t}];
    res = -(1e9 + 7);

    if (t == 0 && left >= 4)
        res = max(res, left - 4 - rec(i, j, 4, -1));
    if (t == 1 && left > 2)
        res = max(res, left - 2 - rec(i, j, 2, -1));
    if (i + 1 < (int)cycle.size())
        res = max(res, left - rec(i + 1, j, cycle[i + 1], 0));
    if (j + 1 < (int)path.size())
        res = max(res, left - rec(i, j + 1, path[j + 1], 1));

    return res;
}

void dfs(int u)
{
    used[u] = 1;
    cntv++;
    cnte += (int)edges[u].size();
    for (auto x : edges[u])
    {
        if (used[x])
            continue;
        dfs(x);
    }
}

signed main()
{
    int n, m;
    cin >> n >> m;
    vector<string> h(n + 1), v(n);
    for (int i = 0; i < n + 1; i++)
        cin >> h[i];
    for (int i = 0; i < n; i++)
        cin >> v[i];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int u = i * m + j;
            if (i && h[i][j] == '0')
                edges[u].push_back(u - m);
            if (i + 1 < n && h[i + 1][j] == '0')
                edges[u].push_back(u + m);
            if (j && v[i][j] == '0')
                edges[u].push_back(u - 1);
            if (j + 1 < m && v[i][j + 1] == '0')
                edges[u].push_back(u + 1);
            if (h[i][j] == '1' && h[i + 1][j] == '1' && v[i][j] == '1' && v[i][j + 1] == '1')
                used[i * m + j] = 1;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int u = i * m + j;
            if (used[u])
                continue;
            cnte = cntv = 0;
            dfs(u);
            if (cntv * 2 > cnte)
                path.push_back(cntv);
            else
                cycle.push_back(cntv);
        }
    }

    sort(path.begin(), path.end());
    sort(cycle.begin(), cycle.end());

    cout << rec(-1, -1, 0, -1) << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20