Submission #242606

#	Time	Username	Problem	Language	Result	Execution time	Memory
242606		valerikk	T-Covering (eJOI19_covering)	C++17	25 / 100	85 ms	12408 KiB

covering

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

const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, 1, 0, -1};
const int INF = 1e9 + 5;

int n, m;

bool check(int i, int j)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> a[i][j];
        }
    }
    vector<vector<bool>> used(n, vector<bool>(m, 0));
    int k;
    cin >> k;
    set<int> s;
    for (int _ = 0; _ < k; ++_)
    {
        int r, c;
        cin >> r >> c;
        used[r][c] = 1;
        s.insert(r);
    }
    if (s.size() == 1)
    {
        int r = *s.begin();
        vector<pair<int, int>> t;
        for (int i = 0; i < m; ++i)
        {
            if (used[r][i])
            {
                t.emplace_back(r, i);
            }
        }
        vector<vector<int>> dp(k, vector<int>(4, -INF));
        for (int h = 0; h < 4; ++h)
        {
            bool fl = 1;
            int sum = a[t[0].first][t[0].second];
            for (int h2 = 0; h2 < 4; ++h2)
            {
                if (h != h2)
                {
                    int x = t[0].first + DX[h2], y = t[0].second + DY[h2];
                    if (!check(x, y))
                    {
                        fl = 0;
                        break;
                    }
                    sum += a[x][y];
                }
            }
            if (fl)
            {
                dp[0][h] = sum;
            }
        }
        for (int i = 1; i < k; ++i)
        {
            for (int h = 0; h < 4; ++h)
            {
                bool fl = 1;
                int sum = a[t[i].first][t[i].second];
                for (int h2 = 0; h2 < 4; ++h2)
                {
                    if (h != h2)
                    {
                        int x = t[i].first + DX[h2], y = t[i].second + DY[h2];
                        if (!check(x, y))
                        {
                            fl = 0;
                            break;
                        }
                        sum += a[x][y];
                    }
                }
                if (fl)
                {
                    for (int p = 0; p < 4; ++p)
                    {
                        if (dp[i - 1][p] != -INF)
                        {
                            bool fl2 = 1;
                            for (int h2 = 0; h2 < 4; ++h2)
                            {
                                if (h2 != h)
                                {
                                    for (int p2 = 0; p2 < 4; ++p2)
                                    {
                                        if (p2 != p)
                                        {
                                            if (t[i].first + DX[h2] == t[i - 1].first + DX[p2] && t[i].second + DY[h2] == t[i - 1].second + DY[p2])
                                            {
                                                fl2 = 0;
                                                break;
                                            }
                                        }
                                    }
                                }
                            }
                            if (fl2)
                            {
                                dp[i][h] = max(dp[i][h], dp[i - 1][p] + sum);
                            }
                        }
                    }
                }
            }
        }
        int ans = -INF;
        for (int i = 0; i < 4; ++i)
        {
            ans = max(ans, dp[k - 1][i]);
        }
        if (ans == -INF)
        {
            cout << "No\n";
        }
        else
        {
            cout << ans;
        }
        return 0;
    }
    vector<vector<int>> go(n, vector<int>(m, -1));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (used[i][j])
            {
                for (int h = 0; h < 4; ++h)
                {
                    int x = i + DX[h], y = j + DY[h];
                    if (check(x, y) && used[x][y])
                    {
                        go[i][j] = h;
                        go[x][y] = h ^ 2;
                    }
                }
            }
        }
    }
    vector<vector<int>> cnt(n, vector<int>(m, 0));
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (!used[i][j])
            {
                continue;
            }
            if (go[i][j] == -1)
            {
                int mx = -INF;
                for (int h = 0; h < 4; ++h)
                {
                    int sum = a[i][j];
                    bool fl = 1;
                    for (int h2 = 0; h2 < 4; ++h2)
                    {
                        if (h2 != h)
                        {
                            int x = i + DX[h2], y = j + DY[h2];
                            if (!check(x, y))
                            {
                                fl = 0;
                                break;
                            }
                            sum += a[x][y];
                        }
                    }
                    if (fl)
                    {
                        mx = max(mx, sum);
                    }
                }
                if (mx == -INF)
                {
                    cout << "No\n";
                    return 0;
                }
                ans += mx;
            }
            else
            {
                bool fl = 1;
                int sum = a[i][j];
                ++cnt[i][j];
                for (int h = 0; h < 4; ++h)
                {
                    if (h != go[i][j])
                    {
                        int x = i + DX[h], y = j + DY[h];
                        if (!check(x, y))
                        {
                            fl = 0;
                            break;
                        }
                        sum += a[x][y];
                        ++cnt[x][y];
                    }
                }
                if (!fl)
                {
                    cout << "No\n";
                    return 0;
                }
                ans += sum;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (cnt[i][j] >= 2)
            {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << ans;
    return 0;
}

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