oj.uz

Submission #778486

# Submission time Handle Problem Language Result Execution time Memory
778486 2023-07-10T11:06:50 Z andrei_iorgulescu T-Covering (eJOI19_covering) C++14
50 / 100
 308 ms 12004 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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;
}

bool all_same_row()
{
    for (int i = 2; i <= k; i++)
        if (v[i].first != v[1].first)
            return false;
    return true;
}

int dp[1005][10];///dp[i][j] = cmax sa pun primele i T-uri, ultimul avand rotatia j

bool inters(pair<int,int>p1,int r1,pair<int,int>p2,int r2)
{
    for (int c1 = 1; c1 <= 4; c1++)
    {
        for (int c2 = 1; c2 <= 4; c2++)
        {
            pair<int,int>n1 = {p1.first + cell[r1][c1].first,p1.second + cell[r1][c1].second};
            pair<int,int>n2 = {p2.first + cell[r2][c2].first,p2.second + cell[r2][c2].second};
            if (n1 == n2)
                return true;
        }
    }
    return false;
}

void solve_all_same_row()
{
    sort(v.begin() + 1,v.end());
    for (int r = 1; r <= 4; r++)
    {
        bool boo = true;
        int sm = 0;
        for (int j = 1; j <= 4; j++)
        {
            int l = v[1].first + cell[r][j].first,c = v[1].second + cell[r][j].second;
            if (l == 0 or l == m + 1 or c == 0 or c == m + 1)
                boo = false;
            else
                sm += a[l][c];
        }
        if (boo == true)
            dp[1][r] = sm;
        else
            dp[1][r] = -2e6;
    }
    for (int i = 2; i <= k; i++)
    {
        for (int r = 1; r <= 4; r++)
        {
            bool boo = true;
            int sm = 0;
            for (int j = 1; j <= 4; j++)
            {
                int l = v[i].first + cell[r][j].first,c = v[i].second + cell[r][j].second;
                if (l == 0 or l == m + 1 or c == 0 or c == m + 1)
                    boo = false;
                else
                    sm += a[l][c];
            }
            if (boo == false)
                dp[i][r] = -2e6;
            else
            {
                dp[i][r] = -2e6;
                for (int rant = 1; rant <= 4; rant++)
                    if (dp[i - 1][rant] >= 0 and !inters(v[i - 1],rant,v[i],r))
                        dp[i][r] = max(dp[i][r],dp[i - 1][rant] + sm);
            }
        }
    }
    int mx = max(max(dp[k][1],dp[k][2]),max(dp[k][3],dp[k][4]));
    if (mx < 0)
        cout << "No";
    else
        cout << mx;
}

bool all_subtask3()
{
    for (int i = 1; i <= k; i++)
    {
        for (int j = i + 1; j <= k; j++)
        {
            if (abs(v[i].first - v[j].first) == 2 or abs(v[i].second - v[j].second) == 2)
                return false;
        }
    }
    return true;
}

bool viz[1005];

int get_single(pair<int,int>p)
{
    int mx = -1;
    for (int r = 1; r <= 4; r++)
    {
        bool boo = true;
        int sm = 0;
        for (int j = 1; j <= 4; j++)
        {
            int l = p.first + cell[r][j].first,c = p.second + cell[r][j].second;
            if (l == 0 or l == n + 1 or c == 0 or c == m + 1)
                boo = false;
            else
                sm += a[l][c];
        }
        if (boo == true)
            mx = max(mx,sm);
    }
    return mx;
}

bool in_bounds(pair<int,int>p,int r)
{
    for (int j = 1; j <= 4; j++)
    {
        int l = p.first + cell[r][j].first,c = p.second + cell[r][j].second;
        if (l == 0 or l == n + 1 or c == 0 or c == m + 1)
            return false;
    }
    return true;
}

int get_double(pair<int,int>p1,pair<int,int>p2)
{
    int mx = -1;
    for (int r1 = 1; r1 <= 4; r1++)
    {
        for (int r2 = 1; r2 <= 4; r2++)
        {
            if (!inters(p1,r1,p2,r2) and in_bounds(p1,r1) == true and in_bounds(p2,r2) == true)
            {
                int cr = 0;
                for (int j = 1; j <= 4; j++)
                {
                    int l = p1.first + cell[r1][j].first,c = p1.second + cell[r1][j].second;
                    cr += a[l][c];
                }
                for (int j = 1; j <= 4; j++)
                {
                    int l = p2.first + cell[r2][j].first,c = p2.second + cell[r2][j].second;
                    cr += a[l][c];
                }
                mx = max(mx,cr);
            }
        }
    }
    return mx;
}

void solve_subtask3()
{
    for (int i = 1; i <= k; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= k; j++)
        {
            if (j != i)
            {
                if (abs(v[i].first - v[j].first) <= 1 and abs(v[i].second - v[j].second) <= 1)
                    cnt++;
            }
        }
        if (cnt >= 2)
        {
            cout << "No";
            return;
        }
    }
    ans = 0;
    for (int i = 1; i <= k; i++)
    {
        if (!viz[i])
        {
            int id = -1;
            for (int j = i + 1; j <= k; j++)
            {
                if (abs(v[i].first - v[j].first) <= 1 and abs(v[i].second - v[j].second) <= 1)
                    id = j;
            }
            if (id == -1)
            {
                int cr = get_single(v[i]);
                if (cr == -1)
                {
                    cout << "No";
                    return;
                }
                ans += cr;
            }
            else
            {
                viz[id] = true;
                int cr = get_double(v[i],v[id]);
                if (cr == -1)
                {
                    cout << "No";
                    return;
                }
                ans += cr;
            }
        }
    }
    cout << ans;
}

signed 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;
    }
    solve_subtask3();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 18 ms 3784 KB Output is correct
5 Correct 51 ms 11956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 396 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 5 ms 1488 KB Output is correct
4 Correct 16 ms 3740 KB Output is correct
5 Correct 52 ms 11996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 392 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 7 ms 1496 KB Output is correct
4 Correct 16 ms 3804 KB Output is correct
5 Correct 51 ms 12004 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 320 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 304 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Correct 308 ms 304 KB Output is correct
4 Correct 68 ms 212 KB Output is correct
5 Correct 297 ms 312 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 18 ms 3784 KB Output is correct
5 Correct 51 ms 11956 KB Output is correct
6 Correct 290 ms 396 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 5 ms 1488 KB Output is correct
9 Correct 16 ms 3740 KB Output is correct
10 Correct 52 ms 11996 KB Output is correct
11 Correct 306 ms 392 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 7 ms 1496 KB Output is correct
14 Correct 16 ms 3804 KB Output is correct
15 Correct 51 ms 12004 KB Output is correct
16 Correct 290 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 6 ms 1108 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 676 KB Output is correct
23 Correct 6 ms 1492 KB Output is correct
24 Incorrect 16 ms 3772 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 5 ms 1492 KB Output is correct
4 Correct 18 ms 3784 KB Output is correct
5 Correct 51 ms 11956 KB Output is correct
6 Correct 290 ms 396 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 5 ms 1488 KB Output is correct
9 Correct 16 ms 3740 KB Output is correct
10 Correct 52 ms 11996 KB Output is correct
11 Correct 306 ms 392 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 7 ms 1496 KB Output is correct
14 Correct 16 ms 3804 KB Output is correct
15 Correct 51 ms 12004 KB Output is correct
16 Correct 290 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 6 ms 1108 KB Output is correct
21 Correct 302 ms 304 KB Output is correct
22 Correct 4 ms 320 KB Output is correct
23 Correct 308 ms 304 KB Output is correct
24 Correct 68 ms 212 KB Output is correct
25 Correct 297 ms 312 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 676 KB Output is correct
28 Correct 6 ms 1492 KB Output is correct
29 Incorrect 16 ms 3772 KB Output isn't correct
30 Halted 0 ms 0 KB -