| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 298475 | daniel920712 | 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 <stdio.h>
using namespace std;
int can1[705][705][705]={0};
int can2[705][705][705]={0};
long long count_rectangles(vector< vector<int> > all)
{
int N,M,i,j,k,l,m,n,big=0,ok;
long long ans=0;
N=all.size();
M=all[0].size();
if(N==3)
{
for(i=1;i<M-1;i++)
{
ok=1;
big=0;
for(j=i;j<M-1;j++)
{
if(all[1][j]>=all[0][j]||all[1][j]>=all[2][j]) ok=0;
big=max(big,all[1][j]);
if(ok&&big<min(all[1][i-1],all[1][j+1])) ans++;
}
}
return ans;
}
else if(N<3) return 0;
else
{
for(i=1;i<N;i++)
{
for(j=1;j<M;j++)
{
big=0;
for(k=j;k<M-1;k++)
{
big=max(big,all[i][k]);
if(big<all[i][j-1]&&big<all[i][k+1]) can1[i][j][k]=1;
can1[i][j][k]+=can1[i-1][j][k];
}
}
}
for(i=1;i<M;i++)
{
for(j=1;j<N;j++)
{
big=0;
for(k=j;k<N-1;k++)
{
big=max(big,all[k][i]);
if(big<all[j-1][i]&&big<all[k+1][i]) can2[i][j][k]=1;
can2[i][j][k]+=can2[i-1][j][k];
}
}
}
for(i=1;i<N-1;i++)
{
for(j=i;j<N-1;j++)
{
for(k=1;k<M-1;k++)
{
for(l=k;l<M-1;l++)
{
if(can1[j][k][l]-can1[i-1][k][l]==j-i+1&&can2[l][i][j]-can2[k-1][i][j]==l-k+1) ans++;
}
}
}
}
}
return ans;
}