Submission #349210

#TimeUsernameProblemLanguageResultExecution timeMemory
349210tengiz05Rectangles (IOI19_rect)C++17
50 / 100
1991 ms100844 KiB
#include "rect.h" #ifndef EVAL #include "grader.cpp" #endif #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2505; int n, m, dp[N][N]; vector<vector<int>> a; inline bool check(int r1, int c1, int r2, int c2){ for(int i=r1;i<=r2;i++){ for(int j=c1;j<=c2;j++){ int t = min(min(a[i][c1-1], a[i][c2+1]), min(a[r1-1][j], a[r2+1][j])); if(a[i][j] >= t)return false; } }return true; } int get(int x1,int y1,int x2,int y2){ int res = dp[x2][y2]; if(x1&&y1)res += dp[x1-1][y1-1]; if(x1)res -= dp[x1-1][y2]; if(y1)res -= dp[x2][y1-1]; return res; } ll count_rectangles(vector<vector<int>> a){ ::a = a; n = a.size(); m = a[0].size(); ll ans = 0; if(n*m <= 50000){ for(int i=1;i<n-1;i++){ for(int j=1;j<m-1;j++){ for(int I=i;I<n-1;I++){ for(int J=j;J<m-1;J++){ ans += check(i,j,I,J); } } } }return ans; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ dp[i][j] = a[i][j]; if(j)dp[i][j] += dp[i][j-1]; }for(int j=0;j<m;j++){ if(i)dp[i][j] += dp[i-1][j]; } } for(int i=1;i<n-1;i++){ for(int j=1;j<m-1;j++){ if(a[i][j]==1)continue; if(a[i][j-1]!=1 || a[i-1][j]!=1)continue; int x = i, y = j; while(x+1 < n && a[x+1][j]==0)x++; while(y+1 < m && a[i][y+1]==0)y++; if(get(i,j,x,y) == 0 && get(i-1,j,i-1,y) == y-j+1 && get(x+1,j,x+1,y) == y-j+1 && get(i,j-1,x,j-1) == x-i+1 && get(i,y+1,x,y+1) == x-i+1)ans++; } } 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...