이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "quality.h"
#include "grader.h"
#define maxn 90003
using namespace std;
int tree[4*maxn];
void update(int cx , int cy , int q , int val , int id) {
if(cy < q || q < cx)
return;
tree[id] += val;
if(cx == cy)
return;
int mid = (cx+cy) >> 1;
update(cx,mid,q,val,2*id);
update(mid+1,cy,q,val,2*id+1);
}
int query(int x , int y , int& rem , int id) {
if(tree[id] < rem) {
rem -= tree[id];
return -1;
}
if(x == y)
return x;
int mid = (x+y) >> 1;
int l = query(x,mid,rem,2*id);
if(l != -1)
return l;
return query(mid+1,y,rem,2*id+1);
}
int rectangle(int n, int m, int h, int w, int ar[3001][3001]) {
int mid = (h*w+1)/2 , ans = n*m+1 , N = n*m;
for( int r1 = 0 ; r1 <= n-h ; r1++ ) {
memset(tree,0,sizeof(tree));
int r2 = r1+h-1;
for( int i = r1 ; i <= r2 ; i++ )
for( int j = 0 ; j < w ; j++ )
update(1,N,ar[i][j],1,1);
int rem = mid;
ans = min(ans,query(1,N,rem,1));
for( int c1 = 1 ; c1 <= m-w ; c1++ ) {
int c2 = c1+w-1;
for( int i = r1 ; i <= r2 ; i++ ) {
update(1,N,ar[i][c1-1],-1,1);
update(1,N,ar[i][c2],1,1);
rem = mid;
ans = min(ans,query(1,N,rem,1));
}
}
for( int i = r1 ; i <= r2 ; i++ )
for( int j = m-w ; j < m ; j++ )
update(1,N,ar[i][j],-1,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... |