| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1065083 | aaaaaarroz | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll count_rectangles(vector<vector<int>>& a) {
int n = a.size();
int m = a[0].size();
vector<vector<int>> max_row(n, vector<int>(m, 0));
vector<vector<int>> max_col(n, vector<int>(m, 0));
// Precomputar los máximos en cada fila
for (int i = 0; i < n; ++i) {
for (int j = 1; j < m - 1; ++j) {
max_row[i][j] = max(a[i][j], max_row[i][j - 1]);
}
}
// Precomputar los máximos en cada columna
for (int j = 0; j < m; ++j) {
for (int i = 1; i < n - 1; ++i) {
max_col[i][j] = max(a[i][j], max_col[i - 1][j]);
}
}
ll rec = 0;
// Verificar todos los posibles rectángulos
for (int i = 1; i < n - 1; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = 1; k < m - 1; ++k) {
for (int l = k + 1; l < m - 1; ++l) {
bool valid = true;
// Verificar las celdas en las filas superior e inferior
for (int r = i; r <= j; ++r) {
if (max_col[r][k] < a[r][k - 1] || max_col[r][l] < a[r][l + 1]) {
valid = false;
break;
}
}
if (!valid) continue;
// Verificar las celdas en las columnas izquierda y derecha
for (int c = k; c <= l; ++c) {
if (max_row[i][c] < a[i - 1][c] || max_row[j][c] < a[j + 1][c]) {
valid = false;
break;
}
}
if (valid) {
++rec;
}
}
}
}
}
return rec;
}