Submission #252751

#	Time	Username	Problem	Language	Result	Execution time	Memory
252751		Dilshod_Imomov	Rectangles (IOI19_rect)	C++17	50 / 100	5043 ms	325496 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], mat[N][N], srow[N][N], scol[N][N];
vector < int > row[N], col[N]; 

ll rect( int r1, int c1, int r2, int c2, int r3, int c3, int r4, int c4 ) {
	return sum[r4][c4] - sum[r2 - 1][c2] - sum[r3][c3 - 1] + sum[r1 - 1][c1 - 1];
}

ll subtask_6( vector < vector < int > > a ) {
	int ans = 0;
	int n = a.size(), m = a[0].size();
	for ( int i = 1; i <= n; i++ ) {
		for ( int j = 1; j <= m; j++ ) {
			mat[i][j] = a[i - 1][j - 1];
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i][j];
			srow[i][j] = srow[i][j - 1] + mat[i][j];
		}
	}
	for ( int j = 1; j <= m; j++ ) {
		for ( int i = 1; i <= n; i++ ) {
			scol[j][i] = scol[j][i - 1] + mat[i][j];
		}
	}
	for ( int i = 1; i < n; i++ ) {
		for ( int j = 1; j < m; j++ ) {
			if ( mat[i][j] ) {
				row[i].push_back( j );
				col[j].push_back( i );
				continue;
			}
			if ( col[j].empty() || row[i].empty() ) {
				continue;
			}
			int x = col[j].back(), y = row[i].back();
			int r1 = x, c1 = y, r2 = x, c2 = j + 1;
			int r3 = i + 1, c3 = y, r4 = i + 1, c4 = j + 1;
			// cout << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
			// cout << r3 << ' ' << c3 << ' ' << r4 << ' ' << c4 << '\n';
			int sm = rect(r1, c1, r2, c2, r3, c3, r4, c4) - mat[r1][c1] - mat[r2][c2] - mat[r3][c3] - mat[r4][c4];
			int need = (r3 - r1 - 1) * 2 + (c2 - c1 - 1) * 2;
			// cout << need << '\n';
			int A = srow[r2][c2 - 1] - srow[r1][c1];
			int B = srow[r4][c4 - 1] - srow[r3][c3];
			int C = scol[c3][r3 - 1] - scol[c1][r1];
			int D = scol[c4][r4 - 1] - scol[c2][r2];
			// cout << A << ' '<< B << ' ' << C << " " << D << '\n';
			if ( sm == need && A == B && A == (c2 - c1 - 1) && C == D && C == (r3 - r1 - 1) ) {
				ans++;
			}
		}
	}
	return ans;
}

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] );
		}
	}
	if ( mx <= 1 ) {
		return subtask_6(a);
	}
	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);
}
/*
5 5
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
0 0 0 0 0
*/

Compilation message (stderr)

rect.cpp:114: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: 13 / 13
• Subtask 7: 0 / 28