Submission #348894

#	Time	Username	Problem	Language	Result	Execution time	Memory
348894		tengiz05	Rectangles (IOI19_rect)	C++17	0 / 100	133 ms	46204 KiB

rect

#include "rect.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")
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;
}

ll count_rectangles(vector<vector<int>> a){
	::a = a;
	n = a.size();
	m = a[0].size();
	ll ans = 0;
	if(n*m <= 1){
		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++){
			if(i == 0)dp[i][j]=a[i][j]^1;
			else if(a[i][j] == 0)dp[i][j]=dp[i-1][j]+1;
			else dp[i][j] = 0;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int c=1;
			bool ok = (i+1<n&&dp[i+1][j]==0);
			while(j+1 < m && dp[i][j+1] == dp[i][j]){j++,c++;if(i+1<n&&dp[i+1][j]!=0)ok=false;}
			int lst = j-c;
			if(lst < 0)continue;
			for(int k=0;k<dp[i][j];k++)ok &= (dp[i-k][lst]==0);
			lst = j+1;
			if(lst >= m)continue;
			for(int k=0;k<dp[i][j];k++)ok &= (dp[i-k][lst]==0);
			if(dp[i][j] != 0 && j - c+1 != 0 && j != m-1 && i != n-1 && i != 0 && dp[i][j+1] == 0 && dp[i][j-c] == 0&&ok)ans++;
		}
	}
	return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28