Submission #439146

#	Time	Username	Problem	Language	Result	Execution time	Memory
439146		elazarkoren	T-Covering (eJOI19_covering)	C++17	0 / 100	3 ms	332 KiB

covering

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define x first
#define y second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const ll infinity = 1e18;

int n, m;
set<pii> visited;

ll ans = -1;

void Solve(int i, vii &special, vvi &board, ll curr) {
    if (i == special.size()) {
        chkmax(ans, curr);
        return;
    }
    int x = special[i].x, y = special[i].y;
    if (visited.find({x, y}) != visited.end()) {
        return;
    }
    ll sum = board[x][y];
    int bad = 4;
    if (x && visited.find({x - 1, y}) == visited.end()) {
        sum += board[x - 1][y];
        bad--;
    }
    if (x < n - 1 && visited.find({x + 1, y}) == visited.end()) {
        sum += board[x + 1][y];
        bad--;
    }
    if (y && visited.find({x, y - 1}) == visited.end()) {
        sum += board[x][y - 1];
        bad--;
    }
    if (y < m - 1 && visited.find({x, y + 1}) == visited.end()) {
        sum += board[x][y + 1];
        bad--;
    }
    if (bad > 1) {
        return;
    }
    visited.insert({x, y});
    if (bad == 1) {
        auto it1 = visited.end();
        auto it2 = it1, it3 = it1, it4 = it1;
        if (x && visited.find({x - 1, y}) == visited.end()) {
            it1 = visited.insert({x - 1, y}).x;
        }
        if (x < n - 1 && visited.find({x + 1, y}) == visited.end()) {
            it2 = visited.insert({x + 1, y}).x;
        }
        if (y && visited.find({x, y - 1}) == visited.end()) {
            it3 = visited.insert({x, y - 1}).x;
        }
        if (y < m - 1 && visited.find({x, y + 1}) == visited.end()) {
            it4 = visited.insert({x, y + 1}).x;
        }
        Solve(i + 1, special, board, curr + sum);
        if (it1 != visited.end()) visited.erase(it1);
        if (it2 != visited.end()) visited.erase(it2);
        if (it3 != visited.end()) visited.erase(it3);
        if (it4 != visited.end()) visited.erase(it4);
        return;
    }
    auto it2 = visited.insert({x + 1, y}).x;
    auto it3 = visited.insert({x, y - 1}).x;
    auto it4 = visited.insert({x, y + 1}).x;
    Solve(i + 1, special, board, curr + sum - board[x - 1][y]);
    auto it1 = visited.insert({x - 1, y}).x;
    visited.erase(it2);
    Solve(i + 1, special, board, curr + sum - board[x + 1][y]);
    it2 = visited.insert({x + 1, y}).x;
    visited.erase(it3);
    Solve(i + 1, special, board, curr + sum - board[x][y - 1]);
    it3 = visited.insert({x, y - 1}).x;
    visited.erase(it4);
    Solve(i + 1, special, board, curr + sum - board[x][y + 1]);
    visited.erase(it1), visited.erase(it2), visited.erase(it3);
}

int main() {
    cin >> n >> m;
    vvi board(n, vi(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
    int k;
    cin >> k;
    vii special(k);
    for (int i = 0; i < k; i++) {
        cin >> special[i].x >> special[i].y;
    }
    Solve(0, special, board, 0);
    if (ans == -1) cout << "No";
    else cout << ans;
//    ll ans = 0;
//    while (k--) {
//        int x, y;
//        cin >> x >> y;
//        ll sum = 0, min_val = infinity, bad = 4;
//        if (x) {
//            sum += board[x - 1][y];
//            bad--;
//            chkmin(min_val, board[x - 1][y]);
//        }
//        if (x < n - 1) {
//            sum += board[x + 1][y];
//            bad--;
//            chkmin(min_val, board[x + 1][y]);
//        }
//        if (y) {
//            sum += board[x][y - 1];
//            bad--;
//            chkmin(min_val, board[x][y - 1]);
//        }
//        if (y < m - 1) {
//            sum += board[x][y + 1];
//            bad--;
//            chkmin(min_val, board[x][y + 1]);
//        }
//        ans += sum - min_val + board[x][y];
//        if (bad > 1) {
//            cout << "No";
//            return 0;
//        }
//    }
//    cout << ans;
}

Compilation message (stderr)

covering.cpp: In function 'void Solve(int, vii&, vvi&, ll)':
covering.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if (i == special.size()) {
      |         ~~^~~~~~~~~~~~~~~~~

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