Submission #960617

#	Time	Username	Problem	Language	Result	Execution time	Memory
960617		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	5094 ms	40864 KiB

rect

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

using namespace std;

const int N = 2505;

int n,m;

int A[N][N];
bool yes[N];
int mx[N];
int f(int x,int y){
	for(int j = y;j<m;j++){
		yes[j] = true;
		mx[j] = A[x][j];
	}
	int res = 0;
	for(int i = x;i<n;i++){
		int rmx = 0;
		for(int j = y;j<m;j++){
			rmx = max(rmx, A[i][j]);
			yes[j] &= (rmx < A[i][y-1] && rmx < A[i][j+1]);
		}
		for(int j = y;j<m;j++)mx[j] = max(mx[j], A[i][j]);
		for(int j = y;j<m;j++){
			if(mx[j] >= A[i+1][j])break;
			if(mx[j] >= A[x-1][j])break;
			if(yes[j])res++;
		}
	}
	return res;
}

ll count_rectangles(vector<vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			A[i][j] = a[i-1][j-1];
		}
	}

	int res = 0;
	for(int i = 2;i<n;i++){
		for(int j = 2;j<m;j++){
			res += f(i, j);
		}
	}
	return res;
}

• 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