Submission #641101

#	Time	Username	Problem	Language	Result	Execution time	Memory
641101		LeonaRaging	T-Covering (eJOI19_covering)	C++14	100 / 100	121 ms	26792 KiB

covering

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;

int r, c;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0,-1, 1};
vector<vector<int>> a, dp[2], col;
queue<pair<int,int>> q;

bool ok(int i, int j) {
    return i >= 1 && i <= r && j >= 1 && j <= c;
}

void place(int i, int j, int k) {
    // clog << i << ' ' << j << ' ' << k << '\n';
    for (int p = 0; p < 4; p++)
        if (p != k) {
            int x = i + dx[p], y = j + dy[p];
            if (!ok(x, y) || col[x][y])
                cout << "No", exit(0);
            q.push({x, y});
            col[x][y] = 2;
        }
    col[i][j] = 2;
}

void bfs() {
    while (!q.empty()) {
        int i, j; tie(i, j) = q.front(); q.pop();
        for (int p = 0; p < 4; p++) {
            int x = i + dx[p], y = j + dy[p];
            if (ok(x, y) && abs(col[x][y]) == 1) {
                // if (x == 4 && y == 5) clog << "ok";
                place(x, y, p ^ 1);
                col[x][y] = 2;
            }
        }
    }
}

void dfs(int i, int j, int k) {
    col[i][j] = -1;
    dp[0][i][j] = dp[1][i][j] = -INF;
    for (int p = 0; p < 4; p++) if (k != p) {
        int x = i + 2 * dx[p], y = j + 2 * dy[p];
        if (!ok(x, y)) continue;
        if (col[x][y] == -1) {
            place(i, j, p), bfs();
            return;
        }
        else if (col[x][y] == 1)
            dfs(x, y, p ^ 1);
    }
    for (int p = 0; p < 4; p++) {
        int res = a[i][j];
        for (int d = 0; d < 4; d++) {
        // if (i == 4 && j == 2 && p == 3) clog << db(res) << db(d) << '\n';
            int x = i + 2 * dx[d], y = j + 2 * dy[d];
            if (d == p) {
                if (ok(x, y) && d != k) {
                    res += max(dp[0][x][y], dp[1][x][y]);
                }
            }
            else {
                res += a[i + dx[d]][j + dy[d]];
                if (ok(x, y) && d != k) {
                    res += dp[0][x][y];
                }
            }
        }
        dp[p != k][i][j] = max(dp[p != k][i][j], res);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> r >> c;
    a.resize(r + 4);
    for (int i = 0; i < r + 4; i++)
        a[i].resize(c + 4);
    dp[0] = dp[1] = col = a;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    int k; cin >> k;
    for (int i = 1; i <= k; i++) {
        int x, y; cin >> x >> y;
        x++, y++;
        col[x][y] = 1;
        q.push({x, y});
    }   
    for (int i = 1; i <= r; i++)
        q.push({i, 0}), q.push({i, c + 1});
    for (int j = 1; j <= c; j++) {
        q.push({0, j}), q.push({r + 1, j});
    }
    bfs();
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) if (col[i][j] == 1) {
            if (i > 1 && j > 1 && col[i - 1][j - 1] == 1) {
                place(i, j, 0), bfs();
            }
            if (i > 1 && j < c && col[i - 1][j + 1] == 1)
                place(i, j, 0), bfs();
        }
    int res = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++) if (col[i][j] == 1) {
            dfs(i, j, -1);
            if (col[i][j] == -1) {
                res += dp[1][i][j];
                // clog << dp[1][i][j];
            }
        }
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            if (col[i][j] == 2)
                res += a[i][j];
    cout << res;
    // for (int i = 1; i <= r; i++)
        // for (int j = 1; j <= c; j++)
            // cout << col[i][j] << (j == c ? '\n' : ' ');
    // clog << a[6][2];
}

• 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: 30 / 30