Submission #290422

#	Time	Username	Problem	Language	Result	Execution time	Memory
290422		ChrisT	Rectangles (IOI19_rect)	C++17	37 / 100	927 ms	1048580 KiB

rect

#include <bits/stdc++.h>
//#include "rect.h"
using namespace std;
const int MN = 701;
bool canV[MN][MN][MN], canH[MN][MN][MN];
long long count_rectangles (vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<vector<vector<bool>>> canV(m,vector<vector<bool>>(n,vector<bool>(n)));
	vector<vector<vector<bool>>> canH(n,vector<vector<bool>>(m,vector<bool>(m)));
	vector<vector<vector<int>>> psaV(n,vector<vector<int>>(n,vector<int>(m)));
	vector<vector<vector<int>>> psaH(m,vector<vector<int>>(m,vector<int>(n)));
	for (int i = 1; i + 1 < n; i++) {
		for (int j = 1; j + 1 < m; j++) {
			int mx = a[i][j];
			for (int k = j; k + 1 < m; k++) {
				mx = max(mx,a[i][k]);
				canH[i][j][k] = a[i][j-1] > mx && a[i][k+1] > mx;
			}
		}
	}
	for (int j = 1; j + 1 < m; j++) {
		for (int k = j; k + 1 < m; k++) {
			for (int i = 1; i + 1 < n; i++) {
				psaH[j][k][i] = psaH[j][k][i-1] + !canH[i][j][k];
			}
		}
	}
	for (int i = 1; i + 1 < m; i++) {
		for (int j = 1; j + 1 < n; j++) {
			int mx = a[j][i];
			for (int k = j; k + 1 < n; k++) {
				mx = max(mx,a[k][i]);
				canV[i][j][k] = a[j-1][i] > mx && a[k+1][i] > mx;
			}
		}
	}
	for (int j = 1; j + 1 < n; j++) {
		for (int k = j; k + 1 < n; k++) {
			for (int i = 1; i + 1 < m; i++) {
				psaV[j][k][i] = psaV[j][k][i-1] + !canV[i][j][k];
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i + 1 < n; i++) {
		for (int j = i; j + 1 < n; j++) { //rows[i --> j]
			for (int k = 1; k + 1 < m; k++) {
				for (int l = k; l + 1 < m; l++) { //cols[k --> l]
					ans += psaV[i][j][l] == psaV[i][j][k-1] && psaH[k][l][j] == psaH[k][l][i-1];
				}
			}
		}
	}
	return ans;
}
//int main () {
//	printf ("%lld\n",count_rectangles({{4,8,7,5,6},{7,4,10,3,5},{9,7,20,14,2},{9,14,7,3,6},{5,7,5,2,7},{4,5,13,5,6}}));
//	return 0;
//}

• 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