Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 3005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int r, c, h, w;
- int p[N][N];
- int new_p[N][N];
- int pre[N][N];
- int sub1 = 0;
- int ans = 0;
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> r >> c >> h >> w;
- for(int i=1; i<=r; i++){
- for(int j=1; j<=c; j++){
- cin >> p[i][j];
- sub1 = max(sub1,p[i][j]);
- }
- }
- }
- void sub2(){
- vector<int> val;
- for(int i=1; i<=r; i++){
- for(int j=1; j<=c; j++){
- val.pb(p[i][j]);
- }
- }
- sort(all(val));
- //for(auto x : val) cout << x << ' ';
- //cout << endl;
- cout << val[val.size()/2];
- }
- void solve(int x, int y){
- int u = x + h - 1;
- int v = y + w - 1;
- vector<int> val;
- for(int i=x; i<=u; i++){
- for(int j=y; j<=v; j++){
- val.pb(p[i][j]);
- }
- }
- sort(all(val));
- //cout << x << ' ' << y << ": ";
- //cout << val[val.size()/2] << endl;
- ans = max(ans,val[val.size()/2]);
- }
- void sub3(){
- for(int i=1; i+h-1<=r; i++){
- for(int j=1; j+w-1<=c; j++){
- solve(i,j);
- }
- }
- cout << ans;
- }
- int get_sum(int x, int y, int u, int v){
- return pre[u][v] - pre[u][y-1] - pre[x-1][v] + pre[x-1][y-1];
- }
- bool ok(int val){
- for(int i=1; i<=r; i++){
- for(int j=1; j<=c; j++){
- new_p[i][j] = (p[i][j]<val ? 0 : 1);
- //cout << new_p[i][j] << " \n"[j==c];
- }
- }
- memset(pre, 0, sizeof pre);
- for(int i=1; i<=r; i++){
- for(int j=1; j<=c; j++){
- pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + new_p[i][j];
- }
- }
- ans = 0;
- for(int i=1; i+h-1 <= r; i++){
- for(int j=1; j+w-1 <= c; j++){
- int x = i+h-1;
- int y = j+w-1;
- ans = max(ans,get_sum(i,j,x,y));
- }
- }
- return ans>(h*w/2);
- }
- void proc()
- {
- if (h==w && w==1) cout << sub1;
- else if (h==r && w==c){
- sub2();
- }
- else if (r <= 30 && c <= 30){
- sub3();
- }
- else{
- int lo = 1, hi = r*c;
- while (hi - lo > 0){
- int mid = (lo+hi+1)/2;
- if (ok(mid)){
- lo = mid;
- }
- else hi = mid-1;
- }
- cout << lo;
- }
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement