Submission #229812

#	Time	Username	Problem	Language	Result	Execution time	Memory
229812		cfalas	Quality Of Living (IOI10_quality)	C++14	100 / 100	2550 ms	119152 KiB

quality

#include "quality.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID (l+r)/2
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6

#define T double
typedef complex<T> pt;
#define x real()
#define y imag()
T dot(pt v, pt w) {return (conj(v)*w).x;}
T cross(pt v, pt w) {return (conj(v)*w).y;}
T orient(pt a, pt b, pt c) {return cross(b-a,c-a);}
T dist(pt a, pt b) {return abs(a-b);}

int rectangle(int n, int m, int p, int q, int a[3001][3001]){
	int l=0, r=n*m+1;
	int mi, mm;
	while(l<=r){
		mi = MID;
		int b[n][m] = {};
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(a[i][j]<mi) b[i][j]=-1;
				else if(a[i][j]>mi) b[i][j]=1;
			}
		}
		//cout<<"----------  "<<mi<<"  -------"<<endl;
		int pr[n+1][m+1] = {};
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				pr[i][j] = pr[i][j-1] + pr[i-1][j] -pr[i-1][j-1] + b[i-1][j-1];
				//cout<<setw(2)<<pr[i][j]<<" ";
			}
			//cout<<endl;
		}
		//cout<<endl;
		bool f=  false;
		for(int i=p;i<=n;i++){
			for(int j=q;j<=m;j++){
				//cout<<setw(2)<<pr[i][j]-pr[i-p][j]-pr[i][j-q]+pr[i-p][j-q]<<" ";
				if(pr[i][j]-pr[i-p][j]-pr[i][j-q]+pr[i-p][j-q]<=0) f = true;
			}
			//cout<<endl;
		}
		//cout<<f<<endl;
		if(f) mm=mi, r=mi-1;
		else l = mi+1;
	}
	return mm;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:66:9: warning: 'mm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return mm;
         ^~

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