Submission #418495

#	Time	Username	Problem	Language	Result	Execution time	Memory
418495		Aderfish	Rectangles (IOI19_rect)	C++14	25 / 100	5074 ms	39028 KiB

rect

#include "rect.h"

using namespace std;

vector<vector<int>> b;

bool check_col(int x, int b_y, int t_y){
	for(int y = b_y; y <= t_y; y++){
		if(b[x][y] >= b[x][b_y-1] || b[x][y] >= b[x][t_y+1]) return false;
	}
	return true;
}

bool check_line(int y, int l_x, int r_x){
	for(int x = l_x; x <= r_x; x++){
		if(b[x][y] >= b[l_x-1][y] || b[x][y] >= b[r_x+1][y]) return false;
	}
	return true;
}

bool check_rect(int l_x, int r_x, int b_y, int t_y){
	for(int x = l_x; x <= r_x; x++) if(!check_col(x, b_y, t_y)) return false;
	for(int y = b_y; y <= t_y; y++) if(!check_line(y, l_x, r_x)) return false;

	return true;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int w = a.size();
	int h = a[0].size();

	b = a;

	long long counter = 0;

	for(int l_x = 1; l_x < w-1; l_x++){
		for(int r_x = l_x; r_x < w-1; r_x++){
			for(int b_y = 1; b_y < h-1; b_y++){
				for(int t_y = b_y; t_y < h-1; t_y++){
					if(check_rect(l_x, r_x, b_y, t_y)) counter++;
				}
			}
		}
	}

	return counter;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28