oj.uz

Submission #229812

# Submission time Handle Problem Language Result Execution time Memory
229812 2020-05-06T17:14:38 Z cfalas Quality Of Living (IOI10_quality) C++14
100 / 100
 2550 ms 119152 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 26 ms 3072 KB Output is correct
8 Correct 24 ms 3072 KB Output is correct
9 Correct 24 ms 2944 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 26 ms 3072 KB Output is correct
8 Correct 24 ms 3072 KB Output is correct
9 Correct 24 ms 2944 KB Output is correct
10 Correct 272 ms 22724 KB Output is correct
11 Correct 259 ms 22776 KB Output is correct
12 Correct 129 ms 13560 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 26 ms 3072 KB Output is correct
8 Correct 24 ms 3072 KB Output is correct
9 Correct 24 ms 2944 KB Output is correct
10 Correct 272 ms 22724 KB Output is correct
11 Correct 259 ms 22776 KB Output is correct
12 Correct 129 ms 13560 KB Output is correct
13 Correct 2550 ms 119152 KB Output is correct
14 Correct 2480 ms 119032 KB Output is correct
15 Correct 2302 ms 110580 KB Output is correct