Submission #810929

#	Time	Username	Problem	Language	Result	Execution time	Memory
810929		dxz05	Rectangles (IOI19_rect)	C++17	49 / 100	2807 ms	755124 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 702;

bool good[MaxN][MaxN][MaxN]; // i, l, r -> l..r subarray of i
vector<int> val[MaxN][MaxN];

int cnt[MaxN * MaxN];

long long count_rectangles(vector<vector<int>> A) {
	int n = (int) A.size(), m = (int) A[0].size();

	for (int i = 1; i + 1 < n; i++){
		for (int l = 0; l + 2 < m; l++){
			int mx = A[i][l + 1];
			for (int r = l + 2; r < m; r++){
				if (A[i][l] > mx && A[i][r] > mx){
					good[i][l][r] = true;
				}
				mx = max(mx, A[i][r]);
			}
		}
	}

	for (int j = 0; j < m; j++){
		for (int l = 0; l + 2 < n; l++){
			int mx = A[l + 1][j];
			for (int r = l + 2; r < n; r++){
				if (A[l][j] > mx && A[r][j] > mx){
					val[r][j].push_back(l * n + r);
				}
				mx = max(mx, A[r][j]);
			}
		}
	}

	int ans = 0;
	for (int l = 0; l + 2 < m; l++) for (int r = l + 2; r < m; r++){
		for (int x = 0; x + 2 < n; x++){
			if (!good[x + 1][l][r] || good[x][l][r]) continue;

			vector<int> used_values;

			for (int y = x + 2; y < n; y++){
				for (int j = l + 1; j < r; j++){
					for (int v : val[y][j]){
						if (v / n < x) continue;
						cnt[v]++;
						if (cnt[v] == r - l - 1) ans++;
						used_values.push_back(v);
					}
				}
				if (!good[y][l][r]) break;
			}

			for (int v : used_values){
				cnt[v] = 0;
			}

		}
	}

	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