| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 766221 | Cyber_Wolf | Rectangles (IOI19_rect) | C++17 | 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.
// Problem: P3 - Rectangles
// Contest: DMOJ - IOI '19
// URL: https://dmoj.ca/problem/ioi19p3
// Memory Limit: 1 MB
// Time Limit: 2500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
mt19937 rng(time(NULL));
long long count_rectangles(vector<vector<int>> a)
{
if(a.size() <= 2) return 0;
if(a[0].size() <= 2) return 0;
long long ans = 0;
vector<int> mC(a[0].size()), mR(a.size());
for(int i = 1; i+1 < a.size(); i++)
{
for(int j = 1; j+1 < a[0].size(); j++)
{
for(int k = j; k+1 < a[0].size(); k++) mC[k] = 0;
for(int k = i; k+1 < a.size(); k++)
{
for(int z = i; z+1 < a.size(); z++) mR[z] = 0;
for(int z = j; z+1 < a[0].size(); z++)
{
int f = 0;
for(int l = i; l <= k && (f != 3); l++)
{
mR[l] = max(mR[l], a[l][z]);
if(mR[l] >= a[l][j-1])
{
f |= 3;
}
if(mR[l] >= a[l][z+1])
{
f |= 1;
}
}
mC[z] = max(mC[z], a[k][z]);
for(int l = j; l <= z && (f != 3); l++)
{
if(mC[l] >= a[i-1][l])
{
f |= 3;
}
if(mC[l] >= a[k+1][l])
{
f |= 1;
}
}
if(f == 3) break;
if(f == 1) continue;
ans++;
// cout << i << ' ' << j << ' ' << k << ' ' << z << '\n';
}
}
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
vector<vector<int>> a;
for(int i = 0; i < n; i++)
{
vector<int> x(m);
for(int j = 0; j < m; j++)
{
cin >> x[j];
}
a.push_back(x);
}
cout << count_rectangles(a) << '\n';
return 0;
}