Submission #1212367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212367		segfault_ikuyo	Quality Of Living (IOI10_quality)	C++20	100 / 100	1128 ms	70948 KiB

quality

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

const int maxn=3e3+5;
int pfx[maxn][maxn];

int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
	int l=1,r=R*C,m,mn;
	while(l<r){
		m=(l+r)/2;
		mn=INT_MAX;
		for(int i=1;i<=R;i++){
			for(int j=1;j<=C;j++){
				pfx[i][j]=Q[i-1][j-1]>m;
				pfx[i][j]+=pfx[i-1][j]+pfx[i][j-1]-pfx[i-1][j-1];
			}
		}
		for(int i=H;i<=R;i++){
			for(int j=W;j<=C;j++){
				mn=min(mn,pfx[i][j]-pfx[i-H][j]-pfx[i][j-W]+pfx[i-H][j-W]);
			}
		}
		if(mn<=(H*W)/2) r=m;
		else l=m+1;
	}
	return l;
}

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