Submission #1237193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237193		Sir_Ahmed_Imran	Rectangles (IOI19_rect)	C++17	13 / 100	188 ms	147508 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2503
#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 a[MAXN][MAXN];
int p[MAXN][MAXN];
int r[MAXN][MAXN];
int c[MAXN][MAXN];

int get(int i, int j, int I, int J){
	return p[I][J] - p[i - 1][J] - p[I][j - 1] + p[i - 1][j - 1]; 
}

bool check(int i, int j, int I, int J){
	int ans = get(i - 1, j - 1, I + 1, J + 1);
	ans -= a[I + 1][J + 1] + a[i - 1][J + 1] + a[I + 1][j - 1] + a[i - 1][j - 1];
	return (ans == (2 * (I + J - i - j + 2)));
}

ll count_rectangles(vector<vector<int>> rec){
	int n, m, I, J;
	ll ans = 0;
	n = rec.size();
	m = rec[0].size();
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = rec[i - 1][j - 1];
			p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
		}
	}
	for(int i = n; i > 0; i--){
		for(int j = m; j > 0; j--){
			if(a[i][j] == 0){
				r[i][j] = max(i, r[i + 1][j]);
				c[i][j] = max(j, c[i][j + 1]);
			}
		}
	}
	for(int i = 2; i < n; i++){
		for(int j = 2; j < m; j++){
			if(a[i][j] > 0) continue;
			I = r[i][j], J = c[i][j];
			if(I < n && J < m && get(i, j, I, J) == 0 && check(i, j, I, J))
				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