oj.uz

Submission #778492

# Submission time Handle Problem Language Result Execution time Memory
778492 2023-07-10T11:11:57 Z andrei_iorgulescu T-Covering (eJOI19_covering) C++14
50 / 100
 335 ms 8536 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 and abs(v[i].second - v[j].second) <= 2)
                if (abs(v[i].first - v[j].second) == 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;
    }
    if (all_subtask3() == true)
    {
        solve_subtask3();
        return 0;
    }
    //solve_normal();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 392 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 20 ms 3012 KB Output is correct
5 Correct 54 ms 8536 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 396 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 16 ms 3036 KB Output is correct
5 Correct 51 ms 8536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 400 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 16 ms 3016 KB Output is correct
5 Correct 51 ms 8500 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 312 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 4 ms 676 KB Output is correct
5 Correct 6 ms 1236 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 6 ms 328 KB Output is correct
3 Correct 320 ms 304 KB Output is correct
4 Correct 69 ms 304 KB Output is correct
5 Correct 314 ms 212 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 392 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 20 ms 3012 KB Output is correct
5 Correct 54 ms 8536 KB Output is correct
6 Correct 300 ms 396 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 6 ms 1492 KB Output is correct
9 Correct 16 ms 3036 KB Output is correct
10 Correct 51 ms 8536 KB Output is correct
11 Correct 284 ms 400 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 16 ms 3016 KB Output is correct
15 Correct 51 ms 8500 KB Output is correct
16 Correct 335 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 4 ms 676 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Incorrect 2 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 392 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 20 ms 3012 KB Output is correct
5 Correct 54 ms 8536 KB Output is correct
6 Correct 300 ms 396 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 6 ms 1492 KB Output is correct
9 Correct 16 ms 3036 KB Output is correct
10 Correct 51 ms 8536 KB Output is correct
11 Correct 284 ms 400 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 6 ms 1492 KB Output is correct
14 Correct 16 ms 3016 KB Output is correct
15 Correct 51 ms 8500 KB Output is correct
16 Correct 335 ms 312 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Correct 4 ms 676 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Correct 302 ms 304 KB Output is correct
22 Correct 6 ms 328 KB Output is correct
23 Correct 320 ms 304 KB Output is correct
24 Correct 69 ms 304 KB Output is correct
25 Correct 314 ms 212 KB Output is correct
26 Incorrect 2 ms 340 KB Output isn't correct
27 Halted 0 ms 0 KB -