Submission #1181551

#TimeUsernameProblemLanguageResultExecution timeMemory
1181551jbarejaSandcastle 2 (JOI22_ho_t5)C++20
10 / 100
5094 ms836 KiB
#include <bits/stdc++.h> using namespace std; int H; // liczba wierszy int W; // liczba kolumn vector<vector<int>> height; vector<vector<bool>> visited; vector<pair<int,int>> moves = { {-1,0}, {1,0}, {0,-1}, {0,1} }; bool in_range(int vi, int vj, int i1, int j1, int i2, int j2) { return i1 <= vi && vi <= i2 && j1 <= vj && vj <= j2; } void dfs(int vi, int vj, int i1, int j1, int i2, int j2) { visited[vi][vj] = true; height[0][0] = INT_MIN; int mi = 0, mj = 0; for (const auto& [di, dj]: moves) if (in_range(vi+di,vj+dj, i1,j1, i2,j2) && !visited[vi+di][vj+dj] && height[vi+di][vj+dj] < height[vi][vj]) { if (height[mi][mj] < height[vi+di][vj+dj]) mi = vi+di, mj = vj+dj; } if (mi == 0 && mj == 0) return; dfs(mi,mj, i1,j1, i2,j2); } void visualize(int i1, int j1, int i2, int j2) { for (int i=1; i<=H; i++) { for (int j=1; j<=W; j++) { if (in_range(i,j, i1,j1, i2,j2)) cout << '#'; else cout << '.'; } cout << '\n'; } cout << '\n'; } bool check(int i1, int j1, int i2, int j2) { int vi = i1; int vj = j1; for (int i=i1; i<=i2; i++) for (int j=j1; j<=j2; j++) { visited[i][j] = false; if (height[i][j] > height[vi][vj]) vi = i, vj = j; } dfs(vi,vj, i1,j1, i2,j2); for (int i=i1; i<=i2; i++) for (int j=j1; j<=j2; j++) if (!visited[i][j]) return false; // visualize(i1, j1, i2, j2); return true; } void subtask_2() { int ans = 0; for (int i1=1; i1<=H; i1++) for (int j1=1; j1<=W; j1++) for (int i2=i1; i2<=H; i2++) for (int j2=j1; j2<=W; j2++) ans += check(i1,j1,i2,j2); cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> H >> W; height.assign(H+1, vector<int>(W+1, 0)); visited.assign(H+1, vector<bool>(W+1, false)); for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) cin >> height[i][j]; subtask_2(); }
#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...