| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 730661 | danikoynov | Rectangles (IOI19_rect) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 710;
int n, m;
int h[maxn][maxn], mrow[maxn][maxn][maxn], mcol[maxn][maxn][maxn];
long long count_rectangles(vector<vector<int> > a)
{
n = a.size();
m = a[0].size();
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
h[i][j] = a[i][j];
for (int i = 0; i < n; i ++)
{
for (int j1 = 0; j1 < m; j1 ++)
{
mrow[i][j1][j1] = h[i][j1];
for (int j2 = j1 + 1; j2 < m; j2 ++)
{
mrow[i][j1][j2] = max(mrow[i][j1][j2 - 1], h[i][j2]);
}
}
}
for (int j = 0; j < m; j ++)
for (int i1 = 0; i1 < n; i1 ++)
{
mcol[j][i1][i1] = h[i1][j];
for (int i2 = i1 + 1; i2 < n; i2 ++)
{
mcol[j][i1][i2] = max(mcol[j][i1][i2 - 1], h[i2][j]);
}
}
/**cout << "-----------" << endl;
for (int i = 0; i < n; i ++, cout << endl)
for (int j = 0; j < m; j ++)
cout << h[i][j] << " ";
cout << "-----------" << endl;*/
int ans = 0;
for (int i = 1; i < n - 1; i ++)
for (int j = 1; j < m - 1; j ++)
for (int x = i; x < n - 1; x ++)
for (int y = j; y < m - 1; y ++)
{
/**int i = 4;
int x = 4;
int j = 2;
int y = 3;*/
bool tf = true;
for (int dx = 0; dx <= x - i && tf; dx ++)
{
int mx = mrow[i + dx][j][y], cx = i + dx;
//cout << mx << " " << i + dx << " " << j << " " << y << endl;
if (mx >= h[cx][j - 1] || mx >= h[cx][y + 1])
tf = false;
}
for (int dy = 0; dy <= y - j && tf; dy ++)
{
int mx = mcol[j + dy][i][x], cy = j + dy;
//cout << mx << " " << h[i - 1][cy] << " " << h[x + 1][cy] << endl;
if (mx >= h[i - 1][cy] || mx >= h[x + 1][cy])
tf = false;
}
/**for (int dx = 0; dx <= x - i && tf; dx ++)
for (int dy = 0; dy <= y - j && tf; dy ++)
{
int cx = i + dx, cy = j + dy;
if (h[cx][cy] >= h[cx][j - 1] || h[cx][cy] >= h[cx][y + 1])
tf = false;
if (i == 1 && j == 1 && x == 2 && y == 1)
{
//cout << dx << " : " << dy << " : " << tf << endl;
///cout << h[cx][cy] << " -- " << h[cx][j - 1] << " -- " << h[cx][y + 1] << endl;
}
if (h[cx][cy] >= h[i - 1][cy] || h[cx][cy] >= h[x + 1][cy])
tf = false;
}*/
if (tf)
{
///cout << i << " " << j << " " << x << " " << y << endl;
ans ++;
}
}
return ans;
}