제출 #787508

#제출 시각아이디문제언어결과실행 시간메모리
787508WLZSandcastle 2 (JOI22_ho_t5)C++17
15 / 100
5065 ms3216 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; int main() { ios::sync_with_stdio(false); cin.tie(0); int h, w; cin >> h >> w; vector< vector<int> > grid(h + 2, vector<int>(w + 2)); map<int, int> cmp_mp; for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> grid[i][j], cmp_mp[grid[i][j]] = -1; int cnt = 1; for (auto &p : cmp_mp) p.second = cnt++; for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) grid[i][j] = cmp_mp[grid[i][j]]; auto brute_force = [&](int r1, int c1, int r2, int c2) { int r = r1, c = c1; for (int nr = r1; nr <= r2; nr++) for (int nc = c1; nc <= c2; nc++) if (grid[nr][nc] > grid[r][c]) r = nr, c = nc; int cnt = 0; while (true) { cnt++; int mx = -INF, nr = -1, nc = -1; for (int k = 0; k < 4; k++) { int nnr = r + dx[k], nnc = c + dy[k]; if (nnr >= r1 && nnr <= r2 && nnc >= c1 && nnc <= c2 && grid[nnr][nnc] < grid[r][c] && grid[nnr][nnc] > mx) { mx = grid[nnr][nnc]; nr = nnr, nc = nnc; } } r = nr, c = nc; if (mx == -INF) break; } return cnt == (r2 - r1 + 1) * (c2 - c1 + 1); }; int ans = 0; for (int r1 = 1; r1 <= h; r1++) { for (int c1 = 1; c1 <= w; c1++) { for (int r2 = r1; r2 <= h; r2++) { for (int c2 = c1; c2 <= w; c2++) { ans += brute_force(r1, c1, r2, c2); } } } } cout << ans << '\n'; return 0; }
#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...