#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;
}
void make(int num)
{
for (int i = 0; i < 3001; i++)
{
for (int j = 0; j < 3001; 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 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 = 1; i <= r * c; i++)
{
make(i - 1);
if (good(i)) return i;
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2440 ms |
71072 KB |
Output is correct |
2 |
Correct |
2679 ms |
71232 KB |
Output is correct |
3 |
Correct |
2535 ms |
71072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2440 ms |
71072 KB |
Output is correct |
2 |
Correct |
2679 ms |
71232 KB |
Output is correct |
3 |
Correct |
2535 ms |
71072 KB |
Output is correct |
4 |
Execution timed out |
5059 ms |
71404 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2440 ms |
71072 KB |
Output is correct |
2 |
Correct |
2679 ms |
71232 KB |
Output is correct |
3 |
Correct |
2535 ms |
71072 KB |
Output is correct |
4 |
Execution timed out |
5059 ms |
71404 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2440 ms |
71072 KB |
Output is correct |
2 |
Correct |
2679 ms |
71232 KB |
Output is correct |
3 |
Correct |
2535 ms |
71072 KB |
Output is correct |
4 |
Execution timed out |
5059 ms |
71404 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2440 ms |
71072 KB |
Output is correct |
2 |
Correct |
2679 ms |
71232 KB |
Output is correct |
3 |
Correct |
2535 ms |
71072 KB |
Output is correct |
4 |
Execution timed out |
5059 ms |
71404 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |