Submission #1174980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174980		vahagng	Quality Of Living (IOI10_quality)	C++20	0 / 100	1 ms	320 KiB

quality

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

#define ll long long
#define all(v) v.begin(),v.end()

int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
	auto check = [&](ll x){
		vector<vector<int>> g(n, vector<int>(m, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				g[i][j] = a[i-1][j-1] <= x ? 1 : -1;
				if (i != 0) g[i][j] += g[i-1][j];
				if (j != 0) g[i][j] += g[i][j-1];
				if (i != 0 && j != 0) g[i][j] -= g[i-1][j-1];
			}
		}
		auto qry = [&](int x1, int y1, int x2, int y2) {
			int sum = g[x2][y2];
			if (x1 != 0) sum -= g[x1 - 1][y2];
			if (y1 != 0) sum -= g[x2][y1 - 1];
			if (x1 != 0 && y1 != 0) sum += g[x1 - 1][y1 - 1];
			return sum;
		};
		int mx = -h*w;
		for (int x1 = 0, x2 = h-1; x2 < n; x1++, x2++) {
			for (int y1 = 0, y2 = w-1; y2 < m; y1++, y2++) {
				int s = qry(x1, y1, x2, y2);
				mx = max(mx, s);
			}
		}
		return mx;
	};
    for(int i = 1; i <= n*m; i++){
		if(check(i) > 0) return i;
	}
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20