Submission #1215384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215384		brinton	Rectangles (IOI19_rect)	C++20	13 / 100	472 ms	400504 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

long long count_rectangles(vector<vector<int> > a) {
	int N = a.size(),M = a[0].size();

	vector<vector<bool>> vis(N,vector<bool>(M,false));

	int li,ri,lj,rj;
	int cnt;

	int di[4] = {1,0,-1,0};
	int dj[4] = {0,1,0,-1};
	function<void(int,int)> fill_up = [&](int i,int j){
		li = min(li,i), lj = min(lj,j);
		ri = max(ri,i), rj = max(rj,j);
		cnt++;
		
		for(int d = 0;d < 4;d++){
			int ni = i+di[d];
			int nj = j+dj[d];
			if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
			if(a[ni][nj] == 1) continue;
			if(vis[ni][nj]) continue;
			vis[ni][nj] = true;
			fill_up(ni,nj);
		}
	};
	long long ans = 0;
	for(int i = 0;i < N;i++){
		for(int j = 0;j < M;j++){
			if(a[i][j] == 1 || vis[i][j]) continue;
			li = i,ri = i,lj = j,rj = j,cnt = 0;
			vis[i][j] = true;
			fill_up(i,j);
			if(li == 0 || lj == 0 || ri == N-1 || rj == M-1) continue;
			if((ri-li+1)*(rj-lj+1) != cnt) continue;
			// cout << i << " " << j << endl;
			ans++;
		}
	}
	return ans;
}

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