이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> >precompute(int n, int m, vector<vector<int> >&massiv)
{
vector<vector<int> >preff(n + 1, vector<int>(m + 1));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
preff[i + 1][j + 1] = preff[i][j + 1] + preff[i + 1][j] + massiv[i][j] - preff[i][j];
}
}
return preff;
}
int query(int lx, int ly, int rx, int ry, vector<vector<int> >&preff)
{
return preff[rx][ry] - preff[rx][ly - 1] - preff[lx - 1][ry] + preff[lx - 1][ly - 1];
}
int f(int pos)
{
return pos * (pos + 1) / 2;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<vector<int> >prefsum(R + 1, vector<int>(C + 1));
int l = 1;
int r = R * C;
vector<vector<int> >tmp;
for(int i = 0; i < R; i++)
{
vector<int>row;
for(int j = 0; j < C; j++)
{
row.push_back(Q[i][j]);
}
tmp.push_back(row);
}
int ans = R * C;
while(l <= r)
{
int mid = l + (r - l) / 2;
int lim = H * W / 2 + 1;
vector<vector<int> >tmp1 = tmp;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
if(tmp1[i][j] > mid)tmp1[i][j] = 0;
else tmp1[i][j] = 1;
}
}
vector<vector<int> >preff = precompute(R, C, tmp1);
int sig = 0;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
if(i + H - 1 < R && j + W - 1 < C)
{
int sum = query(i + 1, j + 1, i + H, j + W, preff);
if(sum == lim)
{
sig = 1;
break;
}
}
}
if(sig)break;
}
if(sig){ans = min(ans, mid); r = mid - 1;}
else l = mid + 1;
}
return ans;
}
# | 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... |