Submission #834625

#	Time	Username	Problem	Language	Result	Execution time	Memory
834625		gromperen	Rectangles (IOI19_rect)	C++14	37 / 100	5091 ms	61176 KiB

rect

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

#define ll long long

using namespace std;

bool check(int a, int b, int c, int d, vector<vector<int>> &grid) {
	for (int i = a; i <= c; ++i) {
		for (int j = b; j <= d; ++j) {
			if (grid[i][j] >= min({grid[a-1][j], grid[c+1][j], grid[i][b-1], grid[i][d+1]}))
				return false;
		}
	}
	return true;
}

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	ll ans = 0;
	for (int i = 1; i < n-1; ++i) {
		for (int j = 1; j < m-1; ++j) {
			if (a[i-1][j] <= a[i][j]) continue;
			if (a[i][j-1] <= a[i][j]) continue;
			for (int p = i; p < n-1; ++p) {
				if (a[p][j-1] <= a[p][j]) break;
				for (int q = j; q < m-1; ++q) {
					//if (a[i-1][q] <= a[i][q]) break;
					//if (a[p+1][q] <= a[p][q]) break;
					//if (a[p][q+1] <= a[p][q]) break;
					if (check(i,j,p,q, a)) {
						ans++;
						//cout << i << " " << j << " " << p << " " << q << "\n";
					}
				}
			}
		}
	}

	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