#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 |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
828 KB |
Output is correct |
5 |
Correct |
2 ms |
832 KB |
Output is correct |
6 |
Correct |
2 ms |
832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
828 KB |
Output is correct |
5 |
Correct |
2 ms |
832 KB |
Output is correct |
6 |
Correct |
2 ms |
832 KB |
Output is correct |
7 |
Correct |
24 ms |
3084 KB |
Output is correct |
8 |
Correct |
21 ms |
3088 KB |
Output is correct |
9 |
Correct |
19 ms |
2900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
828 KB |
Output is correct |
5 |
Correct |
2 ms |
832 KB |
Output is correct |
6 |
Correct |
2 ms |
832 KB |
Output is correct |
7 |
Correct |
24 ms |
3084 KB |
Output is correct |
8 |
Correct |
21 ms |
3088 KB |
Output is correct |
9 |
Correct |
19 ms |
2900 KB |
Output is correct |
10 |
Correct |
274 ms |
22768 KB |
Output is correct |
11 |
Correct |
269 ms |
22772 KB |
Output is correct |
12 |
Correct |
140 ms |
13448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
828 KB |
Output is correct |
5 |
Correct |
2 ms |
832 KB |
Output is correct |
6 |
Correct |
2 ms |
832 KB |
Output is correct |
7 |
Correct |
24 ms |
3084 KB |
Output is correct |
8 |
Correct |
21 ms |
3088 KB |
Output is correct |
9 |
Correct |
19 ms |
2900 KB |
Output is correct |
10 |
Correct |
274 ms |
22768 KB |
Output is correct |
11 |
Correct |
269 ms |
22772 KB |
Output is correct |
12 |
Correct |
140 ms |
13448 KB |
Output is correct |
13 |
Correct |
2648 ms |
175400 KB |
Output is correct |
14 |
Correct |
2597 ms |
175340 KB |
Output is correct |
15 |
Correct |
2401 ms |
161380 KB |
Output is correct |