Submission #348078

#	Time	Username	Problem	Language	Result	Execution time	Memory
348078		amunduzbaev	Rectangles (IOI19_rect)	C++14	37 / 100	5098 ms	34880 KiB

rect

#include "rect.h"

//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Pi acos(-1);
#define mod 1e9+7
#define inf 1e18
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
 
const int NN = 2505;

int n, m, a[NN][NN];

bool check(int i, int j, int i1, int j1){
	for(int ii = i; ii<=i1; ii++){
		for(int jj = j; jj<=j1; jj++){
			if(a[ii][jj] >= a[ii][j1+1]){
				return 0;
			}if(a[ii][jj] >= a[ii][j-1]){
				return 0;
			}if(a[ii][jj] >= a[i-1][jj]){
				return 0;
			}if(a[ii][jj] >= a[i1+1][jj]){
				return 0;
			}
		}
	}
	return 1;
}

/*

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

*/

ll count_rectangles(vector<vector<int> > A) {
	n = sz(A);
	m = sz(A[0]);
	int cnt = 0;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			a[i][j] = A[i][j];
		}
	}
	
	for(int i=1;i<n-1;i++){
		for(int j=1;j<m-1;j++){
			for(int l=i;l<n-1;l++){
				for(int k=j;k<m-1;k++){
					cnt += check(i, j, l, k);
				}
			}
		}
	}
	
	return cnt;
}

• 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