oj.uz

Submission #787508

# Submission time Handle Problem Language Result Execution time Memory
787508 2023-07-19T08:45:38 Z WLZ Sandcastle 2 (JOI22_ho_t5) C++17
15 / 100
 5000 ms 3216 KB 
#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;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5065 ms 3216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 4880 ms 468 KB Output is correct
8 Correct 838 ms 468 KB Output is correct
9 Correct 161 ms 384 KB Output is correct
10 Correct 1165 ms 392 KB Output is correct
11 Correct 2599 ms 392 KB Output is correct
12 Correct 2522 ms 428 KB Output is correct
13 Correct 365 ms 392 KB Output is correct
14 Correct 153 ms 364 KB Output is correct
15 Correct 341 ms 396 KB Output is correct
16 Correct 189 ms 332 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 4880 ms 468 KB Output is correct
8 Correct 838 ms 468 KB Output is correct
9 Correct 161 ms 384 KB Output is correct
10 Correct 1165 ms 392 KB Output is correct
11 Correct 2599 ms 392 KB Output is correct
12 Correct 2522 ms 428 KB Output is correct
13 Correct 365 ms 392 KB Output is correct
14 Correct 153 ms 364 KB Output is correct
15 Correct 341 ms 396 KB Output is correct
16 Correct 189 ms 332 KB Output is correct
17 Execution timed out 5051 ms 980 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 4880 ms 468 KB Output is correct
8 Correct 838 ms 468 KB Output is correct
9 Correct 161 ms 384 KB Output is correct
10 Correct 1165 ms 392 KB Output is correct
11 Correct 2599 ms 392 KB Output is correct
12 Correct 2522 ms 428 KB Output is correct
13 Correct 365 ms 392 KB Output is correct
14 Correct 153 ms 364 KB Output is correct
15 Correct 341 ms 396 KB Output is correct
16 Correct 189 ms 332 KB Output is correct
17 Execution timed out 5051 ms 980 KB Time limit exceeded
18 Halted 0 ms 0 KB -