제출 #1267682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267682		julia_08	Sandcastle 2 (JOI22_ho_t5)	C++20	10 / 100	5095 ms	1408 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> h;
vector<vector<int>> marc;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int min_x, min_y, max_x, max_y;

bool check(int x, int y){
  return min_x <= x && x <= max_x && min_y <= y && y <= max_y;
}

int cnt;

void dfs(int x, int y){

  marc[x][y] = 1;
  cnt ++;

  int cur_x = -1, cur_y = -1;

  for(int k=0; k<4; k++){

    int nx = x + dx[k], ny = y + dy[k];

    if(check(nx, ny) && !marc[nx][ny]){
      if(cur_x == -1 || h[nx][ny] > h[cur_x][cur_y]){
        cur_x = nx;
        cur_y = ny;
      }
    }

  }

  if(cur_x != -1 && h[cur_x][cur_y] < h[x][y]) dfs(cur_x, cur_y);

}

int solve(int x1, int y1, int x2, int y2){

  min_x = x1;
  max_x = x2;
  min_y = y1;
  max_y = y2;

  int cur_i = x1, cur_j = y1;

  for(int i=x1; i<=x2; i++){
    for(int j=y1; j<=y2; j++){

      if(h[i][j] > h[cur_i][cur_j]){
        cur_i = i;
        cur_j = j;
      }

      marc[i][j] = 0;

    }
  }

  cnt = 0;

  dfs(cur_i, cur_j);

  return (cnt == (x2 - x1 + 1) * (y2 - y1 + 1));

}


int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  h.resize(n + 1, vector<int> (m + 1));
  marc.resize(n + 1, vector<int> (m + 1));

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      cin >> h[i][j];
    }
  }

  int ans = 0;

  for(int x1=1; x1<=n; x1++){
    for(int x2=x1; x2<=n; x2++){
      for(int y1=1; y1<=m; y1++){
        for(int y2=y1; y2<=m; y2++){
          ans += solve(x1, y1, x2, y2);
        }
      }
    }
  }

  cout << ans << "\n";

  return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 0 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20