이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2505;
ll res=0;
int N,M,mat[maxn][maxn],leftt[maxn][maxn],rightt[maxn][maxn],down[maxn][maxn],up[maxn][maxn],prefud[maxn][maxn],preflr[maxn][maxn];
bool checkmat(int i1,int j1,int i2,int j2){
if(i1<=1 or j1<=1 or i2>=N or j2>=M)
return false;
if(i2<i1 or j2<j1)
return false;
/// Suma je 0
for(int i=i1;i<=i2;i++)
if(preflr[i][j2]-preflr[i][j1-1]!=0)
return false;
/// Okruzena 1
if(preflr[i1-1][j2]-preflr[i1-1][j1-1]!=j2-j1+1)
return false;
if(preflr[i2+1][j2]-preflr[i2+1][j1-1]!=j2-j1+1)
return false;
if(prefud[i2][j1-1]-prefud[i1-1][j1-1]!=i2-i1+1)
return false;
if(prefud[i2][j2+1]-prefud[i1-1][j2+1]!=i2-i1+1)
return false;
return true;
}
bool checkgood(int x,int y){
if(mat[x][y]==1)
return false;
int l=leftt[x][y]+1;
int r=rightt[x][y]-1;
int u=up[x][y]+1;
int d=down[x][y]-1;
// cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;
if(l<=0 or r<=0 or u<=0 or d<=0)
return false;
return checkmat(u,l,d,r);
}
ll count_rectangles(std::vector<std::vector<int> > inp) {
N=inp.size();
M=inp[0].size();
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
mat[i][j]=inp[i-1][j-1];
prefud[i][j]=prefud[i-1][j]+mat[i][j];
preflr[i][j]=preflr[i][j-1]+mat[i][j];
}
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
leftt[i][j]=leftt[i][j-1];
if(mat[i][j]==1)
leftt[i][j]=j;
}
for(int j=M;j>=1;j--){
rightt[i][j]=rightt[i][j+1];
if(mat[i][j]==1)
rightt[i][j]=j;
}
}
for(int j=1;j<=M;j++){
for(int i=1;i<=N;i++){
up[i][j]=up[i-1][j];
if(mat[i][j]==1)
up[i][j]=i;
}
for(int i=N;i>=1;i--){
down[i][j]=down[i+1][j];
if(mat[i][j]==1)
down[i][j]=i;
}
}
//cout<<checkgood(4,3)<<endl;
//return 0;
for(int i=2;i<N;i++)
for(int j=2;j<M;j++){
if(mat[i-1][j]!=1)
continue;
if(mat[i][j-1]!=1)
continue;
if(checkgood(i,j))
res++;
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |