Submission #1219558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219558		Aisha	T-Covering (eJOI19_covering)	C++20	15 / 100	1096 ms	912 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    int n, m;
    cin >> n >> m;

    vector <vector <int>> a(n + 1, vector <int> (m + 1));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }

    int k;
    cin >> k;

    vector <int> r(k), c(k);
    for (int i = 0; i < k; i ++) cin >> r[i] >> c[i];

    vector <vector <int>> b(n + 1, vector <int> (m + 1));

    int ans = -1;

    auto check = [&](int x, int y, vector <int> dx, vector <int> dy) -> bool {
        bool ok = true;
        for (int i = 0; i < 4; i ++) {
            if (1 <= dx[i] + x && dx[i] + x <= n && 1 <= dy[i] + y && dy[i] + y <= m && b[dx[i] + x][dy[i] + y] == 0) continue;
            //cout << dx[i] << ' ' << x << endl;
            //cout << dy[i] << ' ' << y << endl;
            ok = false;
        }

        return ok;
    };

    auto f1 = [&](int x, int y, vector <int> dx, vector <int> dy) -> int {
        int sum = 0;
        for (int i = 0; i < 4; i ++) {
            b[dx[i] + x][dy[i] + y] = 1;
            sum += a[dx[i] + x][dy[i] + y];
        }

        return sum;
    };

    auto f0 = [&](int x, int y, vector <int> dx, vector <int> dy) -> int {
        int sum = 0;
        for (int i = 0; i < 4; i ++) {
            b[dx[i] + x][dy[i] + y] = 0;
            sum -= a[dx[i] + x][dy[i] + y];
        }

        return sum;
    };
    
    auto f = [&](auto&& f, int i, int sum) {
        if (i == k) {
            ans = max(ans, sum);
            return;
        }

        int x = r[i] + 1, y = c[i] + 1;
      //  cout << x << ' ' << y << endl;

        if (check(x, y, {-1, 0, 0, 1}, {0, 0, 1, 0})) {
            sum += f1(x, y, {-1, 0, 0, 1}, {0, 0, 1, 0});
            f(f, i + 1, sum);
            sum += f0(x, y, {-1, 0, 0, 1}, {0, 0, 1, 0});
        }
        if (check(x, y, {-1, 0, 0, 1}, {0, -1, 0, 0})) {
            sum += f1(x, y, {-1, 0, 0, 1}, {0, -1, 0, 0});
            f(f, i + 1, sum);
            sum += f0(x, y, {-1, 0, 0, 1}, {0, -1, 0, 0});
        }
        if (check(x, y, {0, 0, 1, 0}, {-1, 0, 0, 1})) {
            sum += f1(x, y, {0, 0, 1, 0}, {-1, 0, 0, 1});
            f(f, i + 1, sum);
            sum += f0(x, y, {0, 0, 1, 0}, {-1, 0, 0, 1});
        }
        if (check(x, y, {0, 0, -1, 0}, {-1, 0, 0, 1})) {
            sum += f1(x, y, {0, 0, -1, 0}, {-1, 0, 0, 1});
            f(f, i + 1, sum);
            sum += f0(x, y, {0, 0, -1, 0}, {-1, 0, 0, 1});
        }
    };

    f(f, 0, 0);
    if (ans == -1) cout << "No" << endl;
    else cout << ans << endl;

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30