Submission #287477

#	Time	Username	Problem	Language	Result	Execution time	Memory
287477		Haunted_Cpp	Rectangles (IOI19_rect)	C++17	15 / 100	1399 ms	51636 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
 
using namespace std;
 
long long count_rectangles(vector<vector<int> > mat) {
  const int r = mat.size();
  const int c = mat[0].size();
  if (r <= 2) {
    return 0;
  }
  if (c <= 2) {
    return 0;
  }
  // Subtask #1 && Subtask #2
  long long res = 0;
  for (int i = 1; i < r - 1; i++) {
    for (int j = 1; j < c - 1; j++) {
      bitset<100> valid;
      valid.set();
      vector<int> col_max(c);
      for (int x = i; x < r - 1; x++) {
        int mx = 0;
        bool valid_state = true;
        for (int z = j; z < c - 1; z++) {
          const int L = mat[x][j - 1];
          const int R = mat[x][z + 1];
          const int up = mat[i - 1][z];
          const int down = mat[x + 1][z];
          mx = max(mx, mat[x][z]);
          col_max[z] = max(col_max[z], mat[x][z]);
          if (mx >= L || mx >= R) valid[z] = 0;
          if (col_max[z] >= up || col_max[z] >= down) valid_state = 0;
          if (mx >= L || mx >= R) continue;
          if (!valid_state) continue;
          if (!valid[z]) continue;
          if (col_max[z] >= up || col_max[z] >= down) continue;
          ++res;
        }
      }
    }
  }
  return res;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28