Submission #252638

#	Time	Username	Problem	Language	Result	Execution time	Memory
252638		Dilshod_Imomov	Rectangles (IOI19_rect)	C++17	37 / 100	5060 ms	67472 KiB

rect

# include <bits/stdc++.h>
# include "rect.h"
# define ll long long
using namespace std;

const int N = 2507;

// bool dp[N][N][N]; // dp[i][j][i1] = 0/1; 1-> can create a rect starting from i,j ending at i1, j
ll sum[N][N];

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size(), m = a[0].size(), ans = 0, mx = 0;
	for ( int i = 1; i <= n; i++ ) {
		for ( int j = 1; j <= m; j++ ) {
			mx = max( mx, a[i - 1][j - 1] );
			sum[i][j] = a[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
	if ( max(n, m) > 200 && mx <= 1 ) {
		vector < int > row[n + 1], col[m + 1];
		for ( int i = 0; i < n - 1; i++ ) {
			for ( int j = 0; j < m - 1; j++ ) {
				if ( a[i][j] ) {
					row[i].push_back( j + 1 );
					col[j].push_back( i + 1 );
				}
				else {
					if ( row[i].empty() || col[j].empty() ) {
						continue;
					}
					int y = row[i].back(), x = col[j].back();
					i++;
					j++;
					int s = (i + 1) - x + 1;
					s *= 2;
					s += ((j + 1) - y - 1) * 2;
					s -= 4;
					s += a[x - 1][y - 1] + a[i][j] + a[x - 1][j] + a[i][y - 1];
					if ( sum[i + 1][j + 1] - sum[x - 1][j + 1] - sum[i + 1][y - 1] + sum[x - 1][y - 1] == s ) {
						// cout << x << ' ' << y << ' ' << i + 1 << ' ' << j + 1 << ' ' << s << '\n';
						ans++;
					}
					i--;
					j--;
				}
			}
		}
		return ans; 
	}
	for ( int i = 1; i < n - 1; i++ ) {
		for ( int j = 1; j < m - 1; j++ ) {
			for ( int i1 = i; i1 < n - 1; i1++ ) {
				for ( int j1 = j; j1 < m - 1; j1++ ) {
					int ok = 1;
					for ( int x = i; x <= i1; x++ ) {
						for ( int y = j; y <= j1; y++ ) {
							int A = a[i - 1][y], B = a[i1 + 1][y];
							int C = a[x][j - 1], D = a[x][j1 + 1];
							int z = a[x][y];
							if ( z >= A || z >= B || z >= C || z >= D ) {
								ok = 0;
								break;
							}
						}
						if ( !ok ) {
							break;
						}
					}
					ans += ok;
				}
			}
		}
	}
	return ans;
}
/*
int32_t main() {
	int n, m;
	cin >> n >> m;
	vector < vector < int >  > a;
	for ( int i = 0; i < n; i++ ) {
		vector < int > vc; 
		for ( int j = 0; j < m; j++ ) {
			int x;
			cin >> x;
			vc.push_back( x );
		}
		a.push_back( vc );
	} 
	cout << count_rectangles(a);
}
/*
6 5
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
0 0 1 0 0
*/

Compilation message (stderr)

rect.cpp:92:1: warning: "/*" within comment [-Wcomment]
 /*

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