Submission #1057675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057675		12345678	Quality Of Living (IOI10_quality)	C++17	100 / 100	732 ms	140368 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=3e3+5;

int qs[nx][nx], l, r;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	l=1, r=R*C;
	while (l<r)
	{
		int md=(l+r)/2, mx=0;
		for (int i=1; i<=R; i++) for (int j=1; j<=C; j++) qs[i][j]=(Q[i-1][j-1]<=md), qs[i][j]+=qs[i-1][j]+qs[i][j-1]-qs[i-1][j-1];
		for (int i=H; i<=R; i++) for (int j=W; j<=C; j++) mx=max(mx, qs[i][j]-qs[i-H][j]-qs[i][j-W]+qs[i-H][j-W]);
		if (mx>=(H*W+1)/2) r=md;
		else l=md+1;
	}
	return l;
}

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