Submission #990057

#	Time	Username	Problem	Language	Result	Execution time	Memory
990057		bachhoangxuan	Quality Of Living (IOI10_quality)	C++17	100 / 100	1122 ms	140368 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int s[maxn][maxn];
int query(int x,int y,int u,int v){
    return s[u][v]-s[x-1][v]-s[u][y-1]+s[x-1][y-1];
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    auto check = [&](int x){
        for(int i=0;i<R;i++) for(int j=0;j<C;j++) s[i+1][j+1]=(Q[i][j]<=x?1:-1);
        for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        for(int i=H;i<=R;i++) for(int j=W;j<=C;j++){
            if(query(i-H+1,j-W+1,i,j)>0) return true;
        }
        return false;
    };
    int l=1,r=R*C,res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

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