Submission #1243284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243284		nvujica	Rectangles (IOI19_rect)	C++20	13 / 100	251 ms	147792 KiB

rect

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

using namespace std;

const int maxn = 2510;

int a[maxn][maxn];
int desno[maxn][maxn];
int dolje[maxn][maxn];
int pref[maxn][maxn];

int suma(int x1, int y1, int x2, int y2){
	return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}

long long count_rectangles(vector<vector<int> > b) {
	int n = b.size();
	int m = b[0].size();

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			a[i + 1][j + 1] = b[i][j];
		}
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + a[i][j];
		}
	}

	// cout << suma(1, 1, 3, 3) << ' ' << suma(2, 2, 2, 2) << endl;

	for(int i = 1; i <= n; i++){
		desno[i][m + 1] = m + 1;

		for(int j = m; j >= 1; j--){
			desno[i][j] = desno[i][j + 1];

			if(a[i][j]) desno[i][j] = j;
		}
	}

	for(int j = 1; j <= m; j++){
		dolje[n + 1][j] = n + 1;

		for(int i = n; i >= 1; i--){
			dolje[i][j] = dolje[i + 1][j];

			if(a[i][j]) dolje[i][j] = i;
		}
	}

	int ans = 0;

	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			if(a[i + 1][j + 1]) continue;

			int r = desno[i + 1][j + 1];
			int d = dolje[i + 1][j + 1];

			if(d == i + 1 || r == j + 1) continue;
            if(d == n + 1 || r == m + 1) continue;


			if(suma(i, j, d, r) - a[i][j] - a[i][r] - a[d][j] - a[d][r] == 2 * (d - i) + 2 * (r - j) - 4 && suma(i + 1, j + 1, d - 1, r - 1) == 0){
                ans++;
                // cout << i << ' ' << j << ' ' << d << ' ' << r << ' ' << pref[6][6] << ' ' << pref[3][6] << ' ' << pref[6][3] << ' ' << pref[3][3] << endl;
            }
		}
	}
	
	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