Submission #778422

#	Time	Username	Problem	Language	Result	Execution time	Memory
778422		andrei_iorgulescu	T-Covering (eJOI19_covering)	C++14	15 / 100	323 ms	468 KiB

covering

#include <bits/stdc++.h>

using namespace std;

int n,m,k;
vector<vector<int>>a;
vector<vector<bool>>b;
vector<pair<int,int>>v;
int ori[15];
pair<int,int>cell[10][10];
int ans = -1;

void afis()
{
    bool bb = true;
    int sm = 0;
    for (int i = 1; i <= k; i++)
    {
        bool boo = true;
        for (int j = 1; j <= 4; j++)
        {
            int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second;
            if (l == 0 or l == n + 1 or c == 0 or c == m + 1)
                boo = false,bb = false;
        }
        if (boo == true)
        {
            for (int j = 1; j <= 4; j++)
            {
                int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second;
                if (!b[l][c])
                    b[l][c] = true,sm += a[l][c];
                else
                    bb = false;
            }
        }
    }
    for (int i = 1; i <= k; i++)
    {
        bool boo = true;
        for (int j = 1; j <= 4; j++)
        {
            int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second;
            if (l == 0 or l == n + 1 or c == 0 or c == m + 1)
                boo = false;
        }
        if (boo == true)
        {
            for (int j = 1; j <= 4; j++)
            {
                int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second;
                b[l][c] = false;
            }
        }
    }
    if (bb == true)
        ans = max(ans,sm);
}

void bkt(int pos)
{
    if (pos == k + 1)
        afis();
    else
    {
        for (int i = 1; i <= 4; i++)
        {
            ori[pos] = i;
            bkt(pos + 1);
        }
    }
}

void solve_small()
{
    b.resize(n + 1);
    for (int i = 1; i <= n; i++)
        b[i].resize(m + 1);
    bkt(1);
    if (ans == -1)
        cout << "No";
    else
        cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        a[i].resize(m + 1);
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    }
    cin >> k;
    v.resize(k + 1);
    for (int i = 1; i <= k; i++)
        cin >> v[i].first >> v[i].second,v[i].first++,v[i].second++;
    cell[1][1] = {0,0},cell[1][2] = {0,-1},cell[1][3] = {0,1},cell[1][4] = {1,0};
    cell[2][1] = {0,0},cell[2][2] = {0,-1},cell[2][3] = {0,1},cell[2][4] = {-1,0};
    cell[3][1] = {0,0},cell[3][2] = {-1,0},cell[3][3] = {0,1},cell[3][4] = {1,0};
    cell[4][1] = {0,0},cell[4][2] = {-1,0},cell[4][3] = {0,-1},cell[4][4] = {1,0};
    if (k <= 10)
    {
        solve_small();
        return 0;
    }
    /*if (all_same_row() == true)
    {
        solve_all_same_row();
        return 0;
    }
    else if (all_subtask2() == true)
    {
        solve_subtask2();
        return 0;
    }
    else
    {
        solve_normal;
        return 0;
    }*/
    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