# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
925495 | 2024-02-11T20:11:01 Z | VMaksimoski008 | Quality Of Living (IOI10_quality) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "quality.h" using namespace std; using ll = long long; int pref[3005][3005]; int rectangle(int n, int m, int r, int c, int q[3005][3005]) { int l=0, r=1e9; int ans = 0; int mat[n+1][m+1]; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) mat[i][j] = q[i-1][j-1]; while(l <= r) { int mid = (l + r) / 2; bool ok = 0; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) pref[i][j] = (mat[i][j] >= mid) + pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1]; for(int i=1; i+r-1<=n; i++) { if(ok) break; for(int j=1; j+c-1<=m; j++) { if(ok) break; ll res = pref[i+r-1][j+c-1] - pref[i-1][j+c-1] - pref[i+r-1][j-1] + pref[i-1][j-1]; if(2 * res >= r * c) ok = 1; } } if(ok) ans = mid, l = mid + 1; else r = mid - 1; } return ans; }