Submission #413844

#	Time	Username	Problem	Language	Result	Execution time	Memory
413844		TLP39	Quality Of Living (IOI10_quality)	C++14	100 / 100	2025 ms	140080 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
int r,c;
int h,w;
int med;
int tot[3001][3001];
int hi,low,av;

bool isntable(int Q[3001][3001])
{
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            tot[i][j]=(int)(Q[i-1][j-1]>=av);
            tot[i][j]+=(tot[i][j-1]+tot[i-1][j]-tot[i-1][j-1]);
        }
    }
    for(int i=h;i<=r;i++)
    {
        for(int j=w;j<=c;j++)
        {
            if(tot[i][j]-tot[i-h][j]-tot[i][j-w]+tot[i-h][j-w]<med) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r=R;
	c=C;
	h=H;
	w=W;
	med=((h*w)+1)>>1;
	hi=r*c+1;
	low=1;
	memset(tot,0,sizeof tot);
	while(hi>low)
    {
        av=(hi+low)>>1;
        if(isntable(Q)) hi=av;
        else low=av+1;
    }
    return hi-1;
}

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