Submission #589479

#	Time	Username	Problem	Language	Result	Execution time	Memory
589479		farhan132	Rectangles (IOI19_rect)	C++17	27 / 100	869 ms	112072 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 203;

ll R_mx[N][N][N], C_mx[N][N][N];

long long count_rectangles(std::vector<std::vector<int> > a) {

	ll n = a.size();
	ll m = a[0].size();
	if(min(n, m) < 3) return 0;

	n -= 2; m -= 2;

	for(ll R = 1; R <= n; R++){
		// len = 1
		for(ll i = 1; i <= m; i++){
			R_mx[R][i][i] = a[R][i];
		}
		for(ll len = 2; len <= m; len++){
			for(ll i = 1; i <= m - len + 1; i++){
				R_mx[R][i][i+len-1] = max(R_mx[R][i][i], R_mx[R][i + 1][i + len - 1]);
			}
		}
	}
	for(ll C = 1; C <= m; C++){
		// len = 1
		for(ll i = 1; i <= n; i++){
			C_mx[C][i][i] = a[i][C];
		}
		for(ll len = 2; len <= n; len++){
			for(ll i = 1; i <= n - len + 1; i++){
				C_mx[C][i][i + len - 1] = max(C_mx[C][i][i], C_mx[C][i + 1][i + len - 1]);
			}
		}
	}
	ll ans = 0;
	for(ll r1 = 1; r1 <= n; r1++){
		for(ll c1 = 1; c1 <= m; c1++){
			for(ll r2 = r1; r2 <= n; r2++){
				for(ll c2 = c1; c2 <= m; c2++){
					// (r1, c1) --- (r2, c2)
					bool ok1 = 1;
				    for(ll i = r1; i <= r2; i++){
				    	if(min(a[i][c1-1], a[i][c2+1]) <= R_mx[i][c1][c2]){
				    		ok1 = 0;
				    		break;
				    	}
				    }
				    if(min(a[r1-1][c2], a[r2+1][c2]) <= C_mx[c2][r1][r2]) break;
				    if(ok1) 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