Submission #404856

#	Time	Username	Problem	Language	Result	Execution time	Memory
404856		Jasiekstrz	Quality Of Living (IOI10_quality)	C++17	100 / 100	2017 ms	86072 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
const int NN=3e3;
int pref[NN+10][NN+10];
int read_p(int x,int y)
{
	if(x<0 || y<0)
		return 0;
	return pref[x][y];
}
void count_pref(int R,int C,int Q[3001][3001],int c)
{
	for(int i=0;i<R;i++)
	{
		for(int j=0;j<C;j++)
			pref[i][j]=read_p(i-1,j)+read_p(i,j-1)-read_p(i-1,j-1)+(Q[i][j]>c);
	}
	return;
}
int min_rec(int R,int C,int H,int W)
{
	int ans=R*C;
	for(int i=H-1;i<R;i++)
	{
		for(int j=W-1;j<C;j++)
			ans=min(ans,read_p(i,j)-read_p(i-H,j)-read_p(i,j-W)+read_p(i-H,j-W));
	}
	return ans;
}
int rectangle(int R,int C,int H,int W,int Q[3001][3001])
{
	int bg=1,en=R*C;
	while(bg<en)
	{
		int mid=(bg+en)/2;
		count_pref(R,C,Q,mid);
		if(min_rec(R,C,H,W)>=(H*W+1)/2)
			bg=mid+1;
		else
			en=mid;
	}
	return bg;
}

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