Submission #1241506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241506		The_Samurai	Rectangles (IOI19_rect)	C++20	37 / 100	616 ms	1114112 KiB

rect

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

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	vector<vector<vector<int>>> pref1(m, vector<vector<int>>(n, vector<int>(n)));
	for (int l = 0; l + 1 < n; l++) {
		for (int j = 1; j + 1 < m; j++) {
			int mx = a[l + 1][j];
			for (int r = l + 2; r < n; r++) {
				pref1[j][l][r] = pref1[j - 1][l][r] + (min(a[l][j], a[r][j]) > mx);
				mx = max(mx, a[r][j]);
			}
		}
	}
	vector<vector<vector<int>>> pref2(n, vector<vector<int>>(m, vector<int>(m)));
	for (int l = 0; l + 1 < m; l++) {
		for (int i = 1; i + 1 < n; i++) {
			int mx = a[i][l + 1];
			for (int r = l + 2; r < m; r++) {
				pref2[i][l][r] = pref2[i - 1][l][r] + (min(a[i][l], a[i][r]) > mx);
				mx = max(mx, a[i][r]);
			}
		}
	}

	ll ans = 0;
	for (int l1 = 0; l1 < n; l1++) {
		for (int r1 = l1 + 2; r1 < n; r1++) {
			for (int l2 = 0; l2 < m; l2++) {
				for (int r2 = l2 + 2; r2 < m; r2++) {
					if (pref1[r2 - 1][l1][r1] - pref1[l2][l1][r1] != r2 - l2 - 1) break;
					ans += pref2[r1 - 1][l2][r2] - pref2[l1][l2][r2] == r1 - l1 - 1;
				}
			}
		}
	}
	return ans;
}

• 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