This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
/// #define int ll
const int oo = 1e9 + 7;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int res = oo, lo = 1, hi = R * C;
while(lo <= hi) {
int md = (lo + hi) / 2; int arr[R][C], dp[R][C]; bool ok = 0;
for(int l = 0; l < R; l++)
for(int i = 0; i < C; i++) {
int v = Q[l][i];
if(v < md) arr[l][i] = 1;
if(v == md) arr[l][i] = 0;
if(v > md) arr[l][i] = -1;
}
for(int l = 0; l < R; l++)
for(int i = 0; i < C; i++) {
dp[l][i] = arr[l][i];
if(l) dp[l][i] += dp[l - 1][i];
if(i) dp[l][i] += dp[l][i - 1];
if(l && i) dp[l][i] -= dp[l - 1][i - 1];
}
for(int l = H - 1; l < R; l++) {
for(int i = W - 1; i < C; i++) {
int calc = dp[l][i];
int lf = l - H, rf = i - W;
if(rf >= 0) calc -= dp[l][rf];
if(lf >= 0) calc -= dp[lf][i];
if(rf >= 0 && lf >= 0)
calc += dp[lf][rf];
if(calc >= 0) ok = 1;
}
}
if(ok) res = md, hi = md - 1;
else lo = md + 1;
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |