# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
229091 | 2020-05-03T11:06:03 Z | thtsshz_bgwrswh | 삶의 질 (IOI10_quality) | C++17 | 0 ms | 0 KB |
#pragma GCC optimize("Ofast") #include<stdio.h> #include<algorithm> using namespace std; int r,c,h,w,num[3005][3005],pre[3005][3005]; bool check(int v){ int i,j; for(i=0;i<r;i++){ for(j=0;j<c;j++){ if(num[i][j]>v) pre[i][j]=1; else if(num[i][j]==v) pre[i][j]=0; else pre[i][j]=-1; } } for(i=0;i<r;i++) for(j=0;j<c;j++) pre[i][j]+=((i&&j)?pre[i-1][j-1]:0)-(j?pre[i][j-1]:0)-(i?pre[i-1][j]:0); for(i=0;i<=r-h;i++) for(j=0;j<=c-w;j++) if(pre[i+h-1][j+c-1]+((i&&j)?pre[i-1][j-1]:0)-(j?pre[i][j-1]:0)-(i?pre[i-1][j]:0)>=0) return 1; return 0; } int rectangle(int R,int C,int H,int W,int Q[3005][3005]){ r=R; c=C; h=H; w=W; int i,j,right=r*c+1,left=0; for(i=0;i<r;i++) for(j=0;j<c;j++) num[i][j]=Q[i][j]; while(right-left>1){ int mid=(right+left)>>1; if(check(mid)) right=mid; else left=mid; } return right; }