Submission #648448

#	Time	Username	Problem	Language	Result	Execution time	Memory
648448		Kirill22	Game (eJOI20_game)	C++17	100 / 100	78 ms	97588 KiB

game

#include "bits/stdc++.h"

using namespace std;

vector<vector<vector<vector<int>>>> dp;

vector<int> a, b;

int solve(int A, int B, int c, int d) {
    if (A == (int) a.size() && B == (int) b.size() && c == 0 && d == 0) {
        return 0;
    }
    vector<int> upda, updb;
    if (A < a.size()) upda = {A};
    if (B < b.size()) updb = {B};
    if (dp[A][B][c][d] == (int) -2e9) {
        for (auto i : upda) {
            dp[A][B][c][d] = max(dp[A][B][c][d], -(a[i] - 4) - solve(A + 1, B, c, d + 1));
        }
        for (auto i : updb) {
            auto tc = c, td = d;
            int L = b[i] / 2, R = b[i] - L, res = 0;
            if (L >= 2) {
                tc++;
                res += L - 2;
            } else if (L) {
                res++;
            }
            if (R >= 2) {
                tc++;
                res += R - 2;
            } else if (R) {
                res++;
            }
            dp[A][B][c][d] = max(dp[A][B][c][d], -res - solve(A, B + 1, tc, td));
        }
        if (c) {
            dp[A][B][c][d] = max(dp[A][B][c][d], abs(2 + solve(A, B, c - 1, d)));
        }
        if (d) {
            dp[A][B][c][d] = max(dp[A][B][c][d], abs(4 + solve(A, B, c, d - 1)));
        }
    }
    return dp[A][B][c][d];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    auto get = [&] (int i, int j) {
        return i * m + j;
    };
    auto check = [&] (int i, int j) {
        return (i >= 0 && i < n && j >= 0 && j < m);
    };
    vector<vector<int>> g(n * m);
    vector<int> cnt(n * m, 4);
    auto add = [&] (int a, int b, int c, int d) {
        if (check(a, b)) {
            cnt[get(a, b)]--;
        }
        if (check(c, d)) {
            cnt[get(c, d)]--;
        }
        if (check(a, b) && check(c, d)) {
            g[get(a, b)].push_back(get(c, d));
            g[get(c, d)].push_back(get(a, b));
        }
    };
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            if (c == '0') {
                add(i - 1, j, i, j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m + 1; j++) {
            char c;
            cin >> c;
            if (c == '0') {
                add(i, j - 1, i, j);
            }
        }
    }
    vector<int> used(n * m);
    int c = 0, was;
    function<void(int)> dfs = [&] (int v) {
        used[v] = 1;
        if ((int) g[v].size() == 1) {
            was = 1;
        }
        c++;
        for (auto u : g[v]) {
            if (!used[u]) {
                dfs(u);
            }
        }
    };
    vector<int> A, B, C, D;
    for (int i = 0; i < n * m; i++) {
        if (cnt[i] != 4 && !used[i]) {
            c = 0, was = 0;
            dfs(i);
            if (was || c == 1) {
                B.push_back(c);
            } else {
                A.push_back(c);
            }
        }
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    a = A, b = B;
    dp.resize((int) a.size() + 1, vector<vector<vector<int>>> ((int) b.size() + 1, vector<vector<int>> ((int) b.size() * 2 + 1,
            vector<int> ((int) a.size() + 1, -(int) 2e9))));
    cout << solve(0, 0, 0, 0);
}

Compilation message (stderr)

game.cpp: In function 'int solve(int, int, int, int)':
game.cpp:14:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (A < a.size()) upda = {A};
      |         ~~^~~~~~~~~~
game.cpp:15:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (B < b.size()) updb = {B};
      |         ~~^~~~~~~~~~

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