Submission #1053371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053371		Nickpapadak	T-Covering (eJOI19_covering)	C++14	15 / 100	1067 ms	776 KiB

covering

#include<bits/stdc++.h>
using namespace std;
#define XX first
#define YY second
const unsigned int MAXK = 1e+6   + 10;
vector<vector<int> > grid;
vector<vector<bool> > sgrid;
vector<pair<int,int> > special;
int N,M, K;

int firsSub(){
    int ans = 0;
    // totalinc = 0/;
    for(int i = 0; i<K; ++i){
        int c = 0;
        int x = special[i].XX, y = special[i].YY;
        int u = 0,r=0,l=0,d=0;
        r += grid[x+1][y];
        r += grid[x][y+1];
        r += grid[x][y-1];

        l += grid[x-1][y];
        l += grid[x][y+1];
        l += grid[x][y-1];

        d += grid[x-1][y];
        d += grid[x+1][y];
        d += grid[x][y+1];

        u += grid[x-1][y];
        u += grid[x+1][y];
        u += grid[x][y-1];
        // int x = special[i].X, y = special[i].Y;
        ans += grid[x][y];
        if(x == 1 ||sgrid[x-1][y]){
            ans += r;
            sgrid[x+1][y] = 1;
            sgrid[x][y+1] = 1;
            sgrid[x][y-1] = 1;
            c++;
        }
        if(x == M || sgrid[x+1][y]){
            ans += l;
            c++;
            sgrid[x-1][y] = 1;
            sgrid[x][y+1] = 1;
            sgrid[x][y-1] = 1;
        }
        if(y == 1 || sgrid[x][y-1]){
            ans += d;
            c++;
            sgrid[x-1][y] = 1;
            sgrid[x+1][y] = 1;
            sgrid[x][y-1] = 1;

        }
        if(y == N || sgrid[x][y+1]){
            ans += u;
            c++;
            sgrid[x-1][y] = 1;
            sgrid[x+1][y] = 1;
            sgrid[x][y-1] = 1;
        }
        if(c>=2) return -1;
        // printf("c: %d  \n", c);
        if(c==1) continue;
        int best = max(l, r);
        best = max(best, u);
        ans += max(best, d);
        // printf("%d s\n", ans);
    }
    return ans;
}
int solve410(int i, vector<vector<bool> > sgrids, int ans);

int Rleft(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[x][d] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}

int Rright(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[x][d] || sgrids[r][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[r][y];
    sgrids[r][y] = 1;
    return solve410(i+1, sgrids, ans);
}

int Rup(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[x][u] || sgrids[r][y] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[x][u];
    sgrids[x][u] = 1;
    ans += grid[r][y];
    sgrids[r][y] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}

int Rdown(int i, vector<vector<bool> > sgrids, int ans){
    int x = special[i].XX, y = special[i].YY;
    int u = y+1, d = y-1, r = x+1, l = x-1;
    if(sgrids[r][y] || sgrids[x][d] || sgrids[l][y]) return -1;
    ans += grid[x][y];
    ans += grid[r][y];
    sgrids[r][y] = 1;
    ans += grid[x][d];
    sgrids[x][d] = 1;
    ans += grid[l][y];
    sgrids[l][y] = 1;
    return solve410(i+1, sgrids, ans);
}

int solve410(int i, vector<vector<bool> > sgrids, int ans){
    if(i>=K){
        // for(int y = 1;y<= N; ++y){
        //     for(int x = 1;x <= M; ++x)
        //         cout << sgrids[x][y] << ' ';
        //     printf("\n");
        // }
        
        return ans;
    }
    // int x = special[i].XX, y = special[i].YY;
    // int u = y+1, d = y-1, r = x+1, l = x-1;
    // printf("%d ", ans);
    return max(max(Rleft(i, sgrids, ans), Rright(i, sgrids, ans)),
    max(Rup(i, sgrids, ans), Rdown(i, sgrids, ans)));
}

int main(){
    scanf("%d%d", &N,&M);// N = y M = x
    grid.resize(M+10, vector<int>(N+10, 0));
    sgrid.resize(M+10, vector<bool>(N+10,0));
    for(int y = 1; y <=N;++y){
        for(int x = 1; x <=M; ++x){
            scanf("%d", &grid[x][y]);
            // printf("done\n");
        }        
    }
    for(int i = 1; i<= M; ++i){
        sgrid[i][0] = 1;
        sgrid[i][N+1] = 1;
    }
    for(int i = 1; i<=N;++i){
        sgrid[0][i] = 1;
        sgrid[M+1][i] = 1;
    }
    scanf("%d", &K);
    for(int i = 1; i<=K; ++i){
        int a,b;
        scanf("%d%d", &a,&b);
        special.push_back({b+1,a+1});
        sgrid[b+1][a+1] = 1;
        // printf("%d\n", grid[a+1][b+1]);
    }
    if(K <= 10){
        int sol =solve410(0, sgrid, 0);
        if(sol == -1) printf("No");
        else          printf("%d", sol);

    }
    else {
    int sol = firsSub();
    if(sol == -1) printf("No");
    else          printf("%d\n", sol);
}
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int Rleft(int, std::vector<std::vector<bool> >, int)':
covering.cpp:78:27: warning: unused variable 'r' [-Wunused-variable]
   78 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                           ^
covering.cpp: In function 'int Rright(int, std::vector<std::vector<bool> >, int)':
covering.cpp:92:36: warning: unused variable 'l' [-Wunused-variable]
   92 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                                    ^
covering.cpp: In function 'int Rup(int, std::vector<std::vector<bool> >, int)':
covering.cpp:106:18: warning: unused variable 'd' [-Wunused-variable]
  106 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |                  ^
covering.cpp: In function 'int Rdown(int, std::vector<std::vector<bool> >, int)':
covering.cpp:120:9: warning: unused variable 'u' [-Wunused-variable]
  120 |     int u = y+1, d = y-1, r = x+1, l = x-1;
      |         ^
covering.cpp: In function 'int main()':
covering.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%d%d", &N,&M);// N = y M = x
      |     ~~~~~^~~~~~~~~~~~~~~
covering.cpp:155:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |             scanf("%d", &grid[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
covering.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     scanf("%d", &K);
      |     ~~~~~^~~~~~~~~~
covering.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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