Submission #431424

#	Time	Username	Problem	Language	Result	Execution time	Memory
431424		APROHACK	Quality Of Living (IOI10_quality)	C++14	80 / 100	5053 ms	175380 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
int Rg, Cg, Hg, Wg;
int sum[3001][3001], q[3001][3001];
unordered_map<int, bool>a;
int sumar(int i, int j, int dd, int htt){
	if(dd<-1||htt<-1)return -1;
	return sum[i][j]-((htt>=0 ? sum[i][htt] : 0)+(dd>=0?sum[dd][j]:0))+(dd>=0&&htt>=0 ? sum[dd][htt] : 0);
}
bool check(int x){
	//cout<<"x =  "<<x<<endl;
	int xd;
	for(int i = 0 ; i < Rg ; i++){

		if(q[i][0]<=x)xd=1;
		else xd=-1;
		sum[i][0]=xd;
		for(int j = 1 ; j < Cg ; j++){
			if(q[i][j]<=x)xd=1;
			else xd=-1;
			sum[i][j]=sum[i][j-1]+xd;
		}
	}
	/*
	for(int i = 0 ; i < Rg ; i ++){
		for(int j = 0 ; j < Cg ; j++){
			cout<<sum[i][j]<<" ";
		}
		cout<<endl;
	}*/
	for(int j = 0 ; j < Cg ; j++){
		sum[0][j];
		if(sumar(0, j, 0-Hg, 0-Wg)>0){
			//cout<<"!"<<0<<" "<<j<<endl;
			return true;
		}
		for(int i = 1 ; i < Rg ; i++){
			sum[i][j]+=sum[i-1][j];
			if(sumar(i, j, i-Hg, j-Wg)>0){
				//cout<<"!"<<i<<" "<<j<<endl;
				return true;
			}
			//cout<<i<<" "<<j<<" = "<<sum[i][j]<<"    ";
		}
		//cout<<endl;
	}
	return false;
	
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	Rg=R, Cg=C, Hg=H, Wg=W;
	int minimum = INT_MAX;
	int li = 1, ls = R*C, pos;
	pos=(li+ls)/2;
	for(int i = 0 ; i < R ; ++i){
		for(int j = 0 ; j < C ; ++j){
			q[i][j]=Q[i][j];
		}
	}
	while(li+1<ls){
		//cout<<li<<" "<<ls<<endl;
		pos=(li+ls)/2;
		a[pos]=check(pos);
		
		if(a[pos])ls=pos;
		else li=pos;
	}
	for(int i = ls ; i >= li ; i--){
		bool dou = ((a.find(i)==a.end())?check(i):a[i]);
		if(dou)pos=i;
	}
	return pos;
}

Compilation message (stderr)

quality.cpp: In function 'bool check(int)':
quality.cpp:34:11: warning: statement has no effect [-Wunused-value]
   34 |   sum[0][j];
      |   ~~~~~~~~^
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:54:6: warning: unused variable 'minimum' [-Wunused-variable]
   54 |  int minimum = INT_MAX;
      |      ^~~~~~~

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