Submission #1237160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237160		Sir_Ahmed_Imran	Rectangles (IOI19_rect)	C++17	27 / 100	1772 ms	125988 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 201
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int r[MAXN][MAXN][MAXN];
int c[MAXN][MAXN][MAXN];
int lr[MAXN][MAXN][MAXN];
int lc[MAXN][MAXN][MAXN];

ll count_rectangles(vector<vector<int>> a){
	int n, m;
	n = a.size();
	m = a[0].size();
	for(int i = 1; i < n - 1; i++)
		for(int j = 1; j < m - 1; j++)
			for(int k = j; k < m - 1; k++)
				c[i][j][k] = max(c[i][j][k - 1], a[i][k]);
	for(int j = 1; j < m - 1; j++)
		for(int i = 1; i < n - 1; i++)
			for(int k = i; k < n - 1; k++)
				r[i][j][k] = max(r[i][j][k - 1], a[k][j]);
	for(int i = n - 2; i > 0; i--)
		for(int j = 1; j < m - 1; j++)
			for(int k = j; k < m - 1; k++)
				if(min(a[i][j - 1], a[i][k + 1]) > c[i][j][k])
					lr[i][j][k] = max(i, lr[i + 1][j][k]);
	for(int j = m - 2; j > 0; j--)
		for(int i = 1; i < n - 1; i++)
			for(int k = i; k < n - 1; k++)
				if(min(a[i - 1][j], a[k + 1][j]) > r[i][j][k])
					lc[i][j][k] = max(j, lc[i][j + 1][k]);
	ll ans = 0;
	for(int i = 1; i < n - 1; i++)
		for(int j = 1; j < m - 1; j++)
			for(int I = i; I < n - 1; I++)
				for(int J = j; J < m -1; J++)
					if(lr[i][j][J] >= I && lc[i][j][I] >= J)
						ans++;
	return ans;
}

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