#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
using namespace std;
const int mn=3001;
bool moze(int r,int c,int h,int w,int q[mn][mn],int kolko)
{
int dp[mn][mn];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) dp[i][j]=0;
if(q[0][0]<kolko) dp[0][0]=1;
for(int i=1;i<r;i++) dp[i][0]=dp[i-1][0]+(q[i][0]<kolko);
for(int j=1;j<c;j++) dp[0][j]=dp[0][j-1]+(q[0][j]<kolko);
for(int i=1;i<r;i++)
{
for(int j=1;j<c;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(q[i][j]<kolko);
}
}
int pola=(h*w)/2;
for(int i=h-1;i<r;i++)
{
for(int j=w-1;j<c;j++)
{
int kolko=dp[i][j];
if(i>=h)
{
kolko-=dp[i-h][j];
}
if(j>=w)
{
kolko-=dp[i][j-w];
}
if(i>=h && j>=w)
{
kolko+=dp[i-h][j-w];
}
if(kolko>=pola) return true;
}
}
return false;
}
int rectangle1(int r,int c,int h,int w,int q[mn][mn])
{
int ll=1,rr=r*c;
while(ll<rr)
{
int mid=(ll+rr)/2;
if(moze(r,c,h,w,q,mid)) rr=mid-1;
else ll=mid+1;
}
return rr;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
return rectangle1(R,C,H,W,Q);
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int r,c,h,w;
cout<<"aaaaa"<<endl;
cin>>r>>c>>h>>w;
int a[mn][mn];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++) cin>>a[i][j];
cout<<rectangle(r,c,h,w,a)<<endl;
return 0;
}*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
