제출 #501130

#제출 시각아이디문제언어결과실행 시간메모리
501130KhizriRectangles (IOI19_rect)C++17
50 / 100
5024 ms523700 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int mxn=2505; int pt,color[mxn][mxn],n,m,rw[mxn],cl[mxn],a,b; int x[4]={0,0,1,-1}; int y[4]={1,-1,0,0}; bool check(int r1,int r2,int c1,int c2,vector<vector<int>>&arr){ for(int i=r1;i<=r2;i++){ for(int j=c1;j<=c2;j++){ if(arr[i][j]<arr[i][c1-1]&&arr[i][j]<arr[i][c2+1]&&arr[i][j]<arr[r1-1][j]&&arr[i][j]<arr[r2+1][j]){ } else{ return false; } } } return true; } int funk(vector<vector<int>>&arr,int x,int y){ int n=(int)arr.size(), m=(int)arr[0].size(); if(arr[x-1][y]<=arr[x][y]||arr[x][y-1]<=arr[x][y]){ return 0; } int ans=0; for(int i=x;i<n-1;i++){ for(int j=y;j<m-1;j++){ if(check(x,i,y,j,arr)){ ans++; } } } return ans; } void dfs(int i,int j,vector<vector<int>>&arr){ color[i][j]=1; if(i==0||i==n-1||j==0||j==m-1){ pt=0; } rw[i]++,cl[j]++; a=max(a,rw[i]),b=max(b,cl[j]); for(int ind=0;ind<4;ind++){ i+=x[ind],j+=y[ind]; if(i>=0&&i<n&&j>=0&&j<m&&!color[i][j]&&!arr[i][j]){ dfs(i,j,arr); } i-=x[ind],j-=y[ind]; } } int task(vector<vector<int>>&arr){ n=arr.size(), m=arr[0].size(); int ans=0; for(int i=1;i<n-1;i++){ for(int j=1;j<m-1;j++){ if(!color[i][j]&&arr[i][j]==0){ pt=1; memset(rw,0,sizeof(rw)); memset(cl,0,sizeof(cl)); a=0,b=0; dfs(i,j,arr); if(pt){ for(int i=0;i<n;i++){ if(rw[i]>0&&rw[i]!=a){ pt=0; break; } } } if(pt){ for(int i=0;i<m;i++){ if(cl[i]>0&&cl[i]!=b){ pt=0; break; } } } ans+=pt; } } } return ans; } long long count_rectangles(vector<vector<int>>arr) { int n=arr.size(), m=arr[0].size(); int ans=0; bool q=true; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(arr[i][j]>1){ q=false; break; } } } if(q){ return task(arr); } for(int i=1;i<n-1;i++){ for(int j=1;j<m-1;j++){ ans+=funk(arr,i,j); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...