Submission #1053342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053342		Nickpapadak	T-Covering (eJOI19_covering)	C++14	0 / 100	2 ms	604 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(sgrid[x-1][y]){
            ans += r;
            c++;
        }
        if(sgrid[x+1][y]){
            ans += l;
            c++;
        }
        if(sgrid[x][y-1]){
            ans += d;
            c++;
        }
        if(sgrid[x][y+1]){
            ans += u;
            c++;
        }
        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+5, vector<int>(N+5, 0));
    sgrid.resize(M+5, vector<bool>(N+5,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[a+1][b+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 main()':
covering.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d%d", &N,&M);// N = y M = x
      |     ~~~~~^~~~~~~~~~~~~~~
covering.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d", &grid[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
covering.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     scanf("%d", &K);
      |     ~~~~~^~~~~~~~~~
covering.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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