Submission #1204848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204848		andrei_n	T-Covering (eJOI19_covering)	C++20	0 / 100	2 ms	580 KiB

covering

#include <bits/stdc++.h>
#define NO cout<<"No"; exit(0);

using namespace std;

const int dx[] = {-1,0,1,0,-1,1,1,-1};
const int dy[] = {0,1,0,-1,1,1,-1,-1};
vector<vector<int>> v;
vector<vector<int>> is;
const int INF = 999999999;

inline bool overlap(int d)
{
    return d == 0 || d == 2 || d == 4 || d == 6;
}

inline void fix(int x, int y)
{
    if(abs(is[x+1][y]) == 1) {NO}
    is[x+1][y] = 2;
    if(abs(is[x-1][y]) == 1) {NO}
    is[x-1][y] = 2;
    if(abs(is[x][y+1]) == 1) {NO}
    is[x][y+1] = 2;
    if(abs(is[x][y-1]) == 1) {NO}
    is[x][y-1] = 2;
}

inline void fix2(int x, int y)
{
    if(abs(is[x+1][y])) {NO}
    is[x+1][y] = 2;
    if(abs(is[x-1][y])) {NO}
    is[x-1][y] = 2;
    if(abs(is[x][y+1])) {NO}
    is[x][y+1] = 2;
    if(abs(is[x][y-1])) {NO}
    is[x][y-1] = 2;
}

void propagate(int x, int y)
{
    if(is[x][y] != -1) return;
    for(int i=0; i<4; ++i)
    {
        if(x+dx[i]*2 < 0 || y+dy[i]*2 < 0) continue;
        if(is[x+dx[i]*2][y+dy[i]*2] == 1)
        {
            fix(x+dx[i]*2, y+dy[i]*2);
            is[x+dx[i]*2][y+dy[i]*2] = -1;
            propagate(x+dx[i]*2, y+dy[i]*2);
        }
//        else if(is[x+dx[i]*2][y+dy[i]*2] != 0)
//            {NO}
    }
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m; cin>>n>>m;
    v.assign(n+3, vector<int>(m+3, INF));
    is.assign(n+3, vector<int>(m+3, 0));
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            cin>>v[i][j];
    for(int i=0; i<=n+2; ++i)
        for(int j=0; j<=m+2; ++j)
            if(i == 0 || i > n || j == 0 || j > m)
                is[i][j] = 2;
    int k; cin>>k;
    for(int i=0; i<k; ++i)
    {
        int x,y; cin>>x>>y; ++x; ++y;
        is[x][y] = 1;
    }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(is[i][j] == 1)
            {
                for(int d=0; d<8; ++d)
                    if(is[i+dx[d]][j+dy[d]] == 1)
                    {
                        is[i+dx[d]][j+dy[d]] = 0;
                        fix(i,j);
                        is[i+dx[d]][j+dy[d]] = -1;
                        is[i][j] = 0;
                        fix(i+dx[d],j+dy[d]);
                        is[i][j] = -1;
                    }
                    else if(is[i+dx[d]][j+dy[d]] == -1) {NO}
            }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            propagate(i, j);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(is[i][j] == 1)
            {
                fix2(i, j);
                is[i][j] = -1;
                int mini = min({v[i-1][j], v[i+1][j], v[i][j+1], v[i][j-1]});
                if(v[i-1][j] == mini)
                    is[i-1][j] = 0;
                else if(v[i+1][j] == mini)
                    is[i+1][j] = 0;
                else if(v[i][j-1] == mini)
                    is[i][j-1] = 0;
                else
                    is[i][j+1] = 0;
            }
    int sum = 0;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(is[i][j] == 2 || is[i][j] == -1)
                sum += v[i][j];
    cout<<sum;
    return 0;
}

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