| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1065099 | 2024-08-18T22:40:10 Z | aaaaaarroz | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll count_rectangles(const vector<vector<int>>& a) {
int n = a.size();
int m = a[0].size();
vector<vector<vector<int>>> maximo_fila(n, vector<vector<int>>(m, vector<int>(n, 0)));
vector<vector<vector<int>>> maximo_columna(n, vector<vector<int>>(m, vector<int>(m, 0)));
for (int k = 1; k < m - 1; ++k) {
for (int i = 1; i < n - 1; ++i) {
for (int j = i; j < n - 1; ++j) {
if (j == i) {
maximo_fila[k][i][j] = a[j][k];
} else {
maximo_fila[k][i][j] = max(a[j][k], maximo_fila[k][i][j - 1]);
}
}
}
}
for (int k = 1; k < n - 1; ++k) {
for (int i = 1; i < m - 1; ++i) {
for (int j = i; j < m - 1; ++j) {
if (j == i) {
maximo_columna[k][i][j] = a[k][j];
} else {
maximo_columna[k][i][j] = max(a[k][j], maximo_columna[k][i][j - 1]);
}
}
}
}
ll rec = 0;
for (int i = 1; i < n - 1; ++i) {
for (int j = i; j < n - 1; ++j) {
for (int k = 1; k < m - 1; ++k) {
for (int l = k; l < m - 1; ++l) {
bool posible = true;
for (int fila = i; fila <= j; ++fila) {
if (maximo_columna[fila][k][l] < a[fila][k - 1] || maximo_columna[fila][k][l] < a[fila][l + 1]) {
posible = false;
break;
}
}
if (!posible) continue;
for (int columna = k; columna <= l; ++columna) {
if (maximo_fila[columna][i][j] < a[i - 1][columna] || maximo_fila[columna][i][j] < a[j + 1][columna]) {
posible = false;
break;
}
}
if (posible) {
++rec;
}
}
}
}
}
return rec;
}