Submission #1241518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241518		The_Samurai	Rectangles (IOI19_rect)	C++20	49 / 100	1931 ms	738864 KiB

rect

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

const int N = 700;
short pref2[N][N][N];
vector<vector<vector<bool>>> pref1(N, vector<vector<bool>>(N, vector<bool>(N)));

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	// vector<basic_string<vector<short>>> pref1(m, vector<vector<short>>(n, vector<short>(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] = (min(a[l][j], a[r][j]) > mx);
				mx = max(mx, a[r][j]);
			}
		}
	}
	// vector<basic_string<vector<short>>> pref2(n, vector<vector<short>>(m, vector<short>(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]) 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: 22 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28