Submission #1088077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088077		StefanSebez	Quality Of Living (IOI10_quality)	C++14	100 / 100	1903 ms	175892 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int rectangle(int n, int m, int H, int W, int a[3001][3001]){
	int A[n+10][m+10];for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) A[i][j]=a[i-1][j-1];
	int l=1,r=n*m,res;
	while(l<=r){
		int mid=l+r>>1;
		//printf("%i %i: %i\n",l,r,mid);
		int pref[n+10][m+10];memset(pref,0,sizeof(pref));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
				//printf("%i ",pref[i][j]);
				if(A[i][j]>mid) pref[i][j]++;
			}
			//printf("\n");
		}
		int mn=n*m+100;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i-H<0 || j-W<0) continue;
				int x=pref[i][j]-pref[i-H][j]-pref[i][j-W]+pref[i-H][j-W];
				mn=min(mn,x);
			}
		}
		if(mn<=H*W/2){
			res=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return res;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:8:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 |   int mid=l+r>>1;
      |           ~^~
quality.cpp:33:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  return res;
      |         ^~~

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