# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861843 | 2023-10-17T04:19:26 Z | sleepntsheep | Quality Of Living (IOI10_quality) | C++17 | 0 ms | 0 KB |
#include <cstdio> #include <cstring> #include <cassert> #include <string> #include <deque> #include <vector> #include <map> #include <queue> #include <algorithm> #include <iostream> #include <utility> using namespace std; using ll=long long; #define ALL(x) x.begin(), x.end() #define N 3086 int n, m, h, w, a[N][N], p[N][N]; int ok(int y) { for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) p[i][j] = (a[i][j] <= y) + p[i-1][j] + p[i][j-1] - p[i-1][j-1]; for (int i = 1; i + h - 1 <= n; ++i) for (int j = 1; j + w - 1 <= m; ++j) if (p[i+h-1][j+w-1] - p[i-1][j+w-1] - p[i+h-1][j-1] + p[i-1][j-1] > (h*w-1)/2) return 1; return 0; } int rectangle(int n, int m, int h, int w, vector<vector<int>> q) { for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = q[i-1][j-1]; int l = 0, r = 1e9; while (l <= r) { int y = (l+r)/2; ok(y) ? r = y - 1 : l = y + 1; } return r+1; }