제출 #737203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737203		NeroZein	Rectangles (IOI19_rect)	C++17	37 / 100	2966 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std; 
 
const int N = 202;
const int M = N * N;
 
const int di[] = {0, 0, 1, -1}; 
const int dj[] = {1, -1, 0, 0};
 
int n, m; 
vector<vector<int>> a;
 
long long count_rectangles(std::vector<std::vector<int> > A) {
	n = (int) A.size(); 
	m = (int) A[0].size(); 
	a = A; 
	vector<vector<vector<int>>> rows(n, vector<vector<int>> (m, vector<int> (m)));
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			int mx = 0; 
			for (int k = j; k < m - 1; ++k) {
				mx = max(mx, a[i][k]);
				rows[i][j][k] = mx; 
			}
		}
	}
	vector<vector<vector<int>>> cols(m, vector<vector<int>> (n, vector<int> (n)));
	for (int i = 1; i < m - 1; ++i) {
		for (int j = 1; j < n - 1; ++j) {
			int mx = 0; 
			for (int k = j; k < n - 1; ++k) {
				mx = max(mx, a[k][i]);
				cols[i][j][k] = mx; 
			}
		}
	}
	auto check = [&](int x, int xx, int y, int yy) {
		for (int i = x; i <= xx; ++i) {
			if (rows[i][y][yy] >= a[i][y - 1] || rows[i][y][yy] >= a[i][yy + 1]) {
				return false; 
			}
		}
		for (int i = y; i <= yy; ++i) {
			if (cols[i][x][xx] >= a[x - 1][i] || cols[i][x][xx] >= a[xx + 1][i]) {
				return false; 
			}
		}
		return true; 
	};
	long long ans = 0; 
	for (int i = 1; i < n - 1; ++i) {
		for (int j = i; j < n - 1; ++j) {
			for (int k = 1; k < m - 1; ++k) {
				for (int l = k; l < m - 1; ++l) {
					ans += check(i, j, k, l); 
				}
			}
		}
	}
	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