Submission #1045193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045193		tosivanmak	Quality Of Living (IOI10_quality)	C++17	100 / 100	816 ms	175388 KiB

quality

// #include "quality.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int grid[3002][3002];
int psum[3002][3002];
ll rr,cc,hh,ww;

ll sum(ll r1, ll c1, ll r2, ll c2){
    return psum[r2][c2]-psum[r2][c1-1]-psum[r1-1][c2]+psum[r1-1][c1-1];
}
bool ck(ll lam){
    for(int i=1;i<=rr;i++){
        for(int j=1;j<=cc;j++){
            psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+(grid[i][j]<=lam);
        }
    }
    for(int i=hh;i<=rr;i++){
        for(int j=ww;j<=cc;j++){
            if(sum(i-hh+1,j-ww+1,i,j)>=(hh*ww+1)/2)return 1;
        }   
    }
    return 0;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    rr=R,cc=C,hh=H,ww=W;
    for(int i=0;i<3001;i++){
        for(int j=0;j<3001;j++){
            grid[i+1][j+1]=Q[i][j];
        }
    }
    ll l=1,r=R*C;
    while(l<r){
        ll mid=(l+r)>>1;
        if(ck(mid))r=mid;
        else l=mid+1;
    }
    return l;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20