Submission #295255

#	Time	Username	Problem	Language	Result	Execution time	Memory
295255		Atill83	Rectangles (IOI19_rect)	C++14	27 / 100	989 ms	82296 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int) 205;

bool hori[MAXN][MAXN][MAXN], verti[MAXN][MAXN][MAXN];
int ph[MAXN][MAXN][MAXN], pv[MAXN][MAXN][MAXN];

long long count_rectangles(vector<vector<int>> a) {
	ll ans = 0;
	int n = a.size();
	int m = a[0].size();
	if(n <= 200 && m <= 200){
		for(int i = 0; i < n; i++){
			for(int j = 0; j + 1 < m; j++){
				int mx = a[i][j + 1];
				for(int l = j + 2; l < m; l++){
					hori[i][j][l] = (min(a[i][l], a[i][j]) > mx);
					mx = max(mx, a[i][l]);
					if(mx > a[i][j]) break;
				}
			}
		}

		for(int j = 0; j < m; j++){
			for(int i = 0; i + 1 < n; i++){
				int mx = a[i + 1][j];
				for(int k = i + 2; k < n; k++){
					verti[i][j][k] = (min(a[k][j] , a[i][j]) > mx);
					mx = max(mx, a[k][j]);
					if(mx > a[i][j]) break;
				}
			}
		}
		for(int l = 3; l <= m; l++){
			for(int j = 0; j <= m - l; j++){
				for(int i = 0; i < n; i++){
					int pre = (i == 0 ? 0 : ph[i - 1][j][l]);
					ph[i][j][l] = pre + hori[i][j][j + l - 1];
				}
			}
		}
		for(int l = 3; l <= n; l++){
			for(int i = 0; i <= n - l; i++){
				for(int j = 0; j < m; j++){
					int pre = (j == 0 ? 0 : pv[i][j - 1][l]);
					pv[i][j][l] = pre + verti[i][j][i + l - 1];
				}
			}
		}

		for(int i = 0; i < n - 2; i++){
			for(int j = 0; j < m - 2; j++){
				for(int k = i + 2; k < n; k++){
					for(int l = j + 2; l < m; l++){
						int d1 = -ph[i][j][l - j + 1] + ph[k - 1][j][l - j + 1];

						int d2 = -pv[i][j][k - i + 1] + pv[i][l - 1][k - i + 1];

						if(d1 == k - i - 1 && d2 == l - j - 1) 
							ans++;
					}
				}
			}
		}

		return ans;
	}

}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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