Submission #434920

#	Time	Username	Problem	Language	Result	Execution time	Memory
434920		Valaki2	T-Covering (eJOI19_covering)	C++14	70 / 100	1090 ms	74728 KiB

covering

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

#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<int, int>
#define pb push_back

int n, m, k;

vector<vector<ll> > values;
vector<vector<bool> > special_cell;
vector<pii> special_cell_list;
vector<vector<bool> > occupied;
vector<vector<bool> > checked;
vector<vector<bool> > working_on;
vector<vector<vector<pii> > > cells_to_remove;

ll answer;

vector<pii> directions = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0)};
vector<pii> directions_adjacent = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0),
                                   mp(1, 1), mp(-1, -1), mp(1, -1), mp(-1, 1),
                                   mp(0, 2), mp(2, 0), mp(0, -2), mp(-2, 0)};

pair<ll, bool> backtrack(int x, int y, pii where_to_remove) {
    checked[x][y] = true;
    working_on[x][y] = true;
    cells_to_remove[where_to_remove.fi][where_to_remove.se].pb(mp(x, y));
    int occupied_cnt = 0;
    if(occupied[x+1][y]) ++occupied_cnt;
    if(occupied[x][y+1]) ++occupied_cnt;
    if(occupied[x-1][y]) ++occupied_cnt;
    if(occupied[x][y-1]) ++occupied_cnt;
    if(occupied_cnt > 1) {
        // working_on[x][y] = false;
        return mp(0ll, false);
    }
    ll maximum_value = 0;
    ll current_value = values[x][y];
    for(pii p : directions) {
        current_value += values[x + p.fi][y + p.se];
    }
    if(occupied_cnt == 1) {
        bool ok = true;
        pii occupied_coords = mp(0, 0);
        for(pii p : directions) {
            if(occupied[x + p.fi][y + p.se]) {
                occupied_coords = p;
            }
            occupied[x + p.fi][y + p.se] = true;
        }
        current_value -= values[x + occupied_coords.fi][y + occupied_coords.se];
        for(pii p : directions_adjacent) {
            if((x + p.fi < 1) || (x + p.fi > n) || (y + p.se < 1) || (y + p.se > m)) continue;
            if(special_cell[x + p.fi][y + p.se] && !working_on[x + p.fi][y + p.se]) {
                pair<ll, bool> result = backtrack(x + p.fi, y + p.se, where_to_remove);
                if(!result.se) {
                    /*for(pii q : directions) {
                        if(q != occupied_coords) {
                            occupied[x + q.fi][y + q.se] = false;
                        }
                    }
                    cells_to_remove[where_to_remove.fi][where_to_remove.se].pb(mp(x, y));
                    working_on[x][y] = false;
                    return mp(0ll, false);*/
                    ok = false;
                }
                current_value += result.fi;
                maximum_value = max(maximum_value, current_value);
            }
        }
        maximum_value = max(maximum_value, current_value);
        for(pii p : directions) {
            if(p != occupied_coords) {
                occupied[x + p.fi][y + p.se] = false;
            }
        }
        // working_on[x][y] = false;
        if(ok) return mp(maximum_value, true);
        else return mp(0ll, false);
    } else {
        bool ok = false;
        for(pii p : directions) {
            occupied[x + p.fi][y + p.se] = true;
        }
        for(pii left_out_coords : directions) {
            occupied[x + left_out_coords.fi][y + left_out_coords.se] = false;
            ll temp_value = current_value;
            current_value -= values[x + left_out_coords.fi][y + left_out_coords.se];
            bool temp_ok = true;
            for(pii p : directions_adjacent) {
                if((x + p.fi < 1) || (x + p.fi > n) || (y + p.se < 1) || (y + p.se > m)) continue;
                if(special_cell[x + p.fi][y + p.se] && !working_on[x + p.fi][y + p.se]) {
                    pair<ll, bool> result = backtrack(x + p.fi, y + p.se, mp(x, y));
                    if(!result.se) {
                        temp_ok = false;
                    }
                    current_value += result.fi;
                }
            }
            occupied[x + left_out_coords.fi][y + left_out_coords.se] = true;
            if(temp_ok) {
                ok = true;
                maximum_value = max(maximum_value, current_value);
            }
            current_value = temp_value;
            if(left_out_coords == directions.back()) continue;
            for(pii p : cells_to_remove[x][y]) {
                working_on[p.fi][p.se] = false;
            }
            cells_to_remove[x][y].clear();
        }
        for(pii p : directions) {
            occupied[x + p.fi][y + p.se] = false;
        }
        for(pii p : cells_to_remove[x][y]) {
            cells_to_remove[where_to_remove.fi][where_to_remove.se].pb(mp(p.fi, p.se));
        }
        cells_to_remove[x][y].clear();
        // working_on[x][y] = false;
        if(!ok) return mp(0ll, false);
        else return mp(maximum_value, true);
    }
}

void solve() {
    cin >> n >> m;
    values.assign(1 + n + 1, vector<ll> (1 + m + 1, 0));
    special_cell.assign(1 + n + 1, vector<bool> (1 + m + 1, false));
    occupied.assign(1 + n + 1, vector<bool> (1 + m + 1, false));
    checked.assign(1 + n + 1, vector<bool> (1 + m + 1, false));
    working_on.assign(1 + n + 1, vector<bool> (1 + m + 1, false));
    cells_to_remove.assign(1 + n + 1, vector<vector<pii> > (1 + m + 1, vector<pii> (0, mp(0, 0))));
    for(int i = 0; i <= n + 1; ++i) {
        occupied[i][0] = true;
        occupied[i][m + 1] = true;
    }
    for(int j = 0; j <= m + 1; ++j) {
        occupied[0][j] = true;
        occupied[n + 1][j] = true;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> values[i][j];
        }
    }
    cin >> k;
    special_cell_list.assign(k, mp(0, 0));
    for(int i = 0; i < k; ++i) {
        cin >> special_cell_list[i].fi >> special_cell_list[i].se;
        ++special_cell_list[i].fi;
        ++special_cell_list[i].se;
        special_cell[special_cell_list[i].fi][special_cell_list[i].se] = true;
        occupied[special_cell_list[i].fi][special_cell_list[i].se] = true;
    }
    for(pii current_cell : special_cell_list) {
        if(!checked[current_cell.fi][current_cell.se]) {
            pair<ll, bool> result = backtrack(current_cell.fi, current_cell.se, mp(0, 0));
            if(!result.se) {
                cout << "No\n";
                return;
            }
            answer += result.fi;
        }
    }
    cout << answer << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
/*
5 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
4
1 1
1 3
3 1
3 3*/

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