제출 #1053395

#제출 시각아이디문제언어결과실행 시간메모리
1053395NickpapadakT-Covering (eJOI19_covering)C++14
0 / 100
5 ms860 KiB
    #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;
                c++;
            }
            if(x == M || sgrid[x+1][y]){
                ans += l;
                c++;
            }
            if(y == 1 || sgrid[x][y-1]){
                ans += d;
                c++;
            }
            if(y == N || sgrid[x][y+1]){
                ans += u;
                c++;
            }
            if(c>=2) return -1;
            // printf("c: %d  \n", c);
        if(sgrid[x+1][y+1] || sgrid[x-1][y+1])
            return c == 0 ?u: -1;
        if(sgrid[x+1][y-1] || sgrid[x-1][y+1])
            return c == 0?d: -1;
            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;
    }

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'int firsSub()':
covering.cpp:55:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |         if(sgrid[x+1][y-1] || sgrid[x-1][y+1])
      |         ^~
covering.cpp:57:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   57 |             if(c==1) continue;
      |             ^~
covering.cpp: In function 'int Rleft(int, std::vector<std::vector<bool> >, int)':
covering.cpp:69:31: warning: unused variable 'r' [-Wunused-variable]
   69 |         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:83:40: warning: unused variable 'l' [-Wunused-variable]
   83 |         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:97:22: warning: unused variable 'd' [-Wunused-variable]
   97 |         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:111:13: warning: unused variable 'u' [-Wunused-variable]
  111 |         int u = y+1, d = y-1, r = x+1, l = x-1;
      |             ^
covering.cpp: In function 'int main()':
covering.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf("%d%d", &N,&M);// N = y M = x
      |         ~~~~~^~~~~~~~~~~~~~~
covering.cpp:146:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |                 scanf("%d", &grid[x][y]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
covering.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf("%d", &K);
      |         ~~~~~^~~~~~~~~~
covering.cpp:161:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |             scanf("%d%d", &a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...