#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int r, c, h, w, q[3001][3001];
int add[3001][3001];
array<int, 2> pos [9000001];
bool cont(int i, int j, int num)
{
auto cpos = pos[num];
if (i <= cpos[0] && cpos[0] <= i + h - 1 && cpos[1] >= j && cpos[1] <= j + w - 1) return true;
return false;
}
bool good(int num)
{
for (int i = 0; i + h - 1 < r; i++)
{
for (int j = 0; j + w - 1 < c; j++)
{
int sum = add[i + h - 1][j + w - 1];
if (i != 0) sum -= add[i - 1][j + w - 1];
if (j != 0) sum -= add[i + h - 1][j - 1];
if (i != 0 && j != 0) sum += add[i - 1][j - 1];
if (sum >= (h * w - 1) / 2 && cont(i, j, num)) return true;
}
}
return false;
}
bool make(int num)
{
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++) add[i][j] = 0;
}
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (q[i][j] <= num) add[i][j] = 1;
if (i != 0) add[i][j] += add[i - 1][j];
if (j != 0) add[i][j] += add[i][j - 1];
if (i != 0 && j != 0) add[i][j] -= add[i - 1][j - 1];
int sum = add[i + h - 1][j + w - 1];
if (i != 0) sum -= add[i - 1][j + w - 1];
if (j != 0) sum -= add[i + h - 1][j - 1];
if (i != 0 && j != 0) sum += add[i - 1][j - 1];
if (sum >= (h * w - 1) / 2 && cont(i, j, num + 1)) return true;
}
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
r = R;
c = C;
h = H;
w = W;
for (int i = 0; i < 3001; i++)
{
for (int j = 0; j < 3001; j++) q[i][j] = Q[i][j];
}
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
pos[q[i][j]] = {i, j};
}
}
for (int i = (h * w - 1) / 2 + 1; i <= r * c; i++)
{
if (make(i - 1)) return i;
}
return -1;
}
Compilation message
quality.cpp: In function 'bool make(int)':
quality.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
61 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
97388 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
97388 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
97388 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
97388 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
137 ms |
97388 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |