oj.uz

Submission #431690

# Submission time Handle Problem Language Result Execution time Memory
431690 2021-06-17T14:31:01 Z APROHACK Quality Of Living (IOI10_quality) C++17
80 / 100
 5000 ms 106044 KB 
#include "quality.h"
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
int Rg, Cg, Hg, Wg;
int sum[3005][3005], q[3005][3005];
//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;
	/*
	for(int i = 0 ; i < Rg ; i++){
		sum[i][0]= 
	}*/
	for(int i = 0 ; i < Rg ; i++){
		sum[i][0]=(q[i][0] <= x ? 1:-1);
		for(int j = 1 ; j < Cg ; j++){
			sum[i][j]=sum[i][j-1]+(q[i][j] <= x ? 1:-1);
		}
	}
	/*
	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(((0-Hg<-1||j-Wg<-1) ? -1 : (sum[0][j]-((j-Wg>=0 ? sum[0][j-Wg] : 0)+(0-Hg>=0?sum[0-Hg][j]:0))+(0-Hg>=0&&j-Wg>=0 ? sum[0-Hg][j-Wg] : 0)))>0)return true;
		for(int i = 1 ; i < Rg ; i++){
			sum[i][j]+=sum[i-1][j];
			if(((i-Hg<-1||j-Wg<-1) ? -1 : (sum[i][j]-((j-Wg>=0 ? sum[i][j-Wg] : 0)+(i-Hg>=0?sum[i-Hg][j]:0))+(i-Hg>=0&&j-Wg>=0 ? sum[i-Hg][j-Wg] : 0)))>0)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!=ls){
		//cout<<li<<" "<<ls<<endl;
		pos=(li+ls)/2;
		//a[pos]=check(pos);
		
		if(check(pos))ls=pos;
		else li=pos+1;
	}
	/*
	for(int i = ls ; i >= li ; i--){
		//bool dou = ((a.find(i)==a.end())?check(i):a[i]);
		if(check(i))pos=i;
	}*/
	return li;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:49:6: warning: unused variable 'minimum' [-Wunused-variable]
   49 |  int minimum = INT_MAX;
      |      ^~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 3 ms 1484 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 3 ms 1484 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 22 ms 4912 KB Output is correct
9 Correct 20 ms 4872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 3 ms 1484 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 22 ms 4912 KB Output is correct
9 Correct 20 ms 4872 KB Output is correct
10 Correct 366 ms 23996 KB Output is correct
11 Correct 294 ms 24176 KB Output is correct
12 Correct 166 ms 18224 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct
5 Correct 3 ms 1484 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 22 ms 4912 KB Output is correct
9 Correct 20 ms 4872 KB Output is correct
10 Correct 366 ms 23996 KB Output is correct
11 Correct 294 ms 24176 KB Output is correct
12 Correct 166 ms 18224 KB Output is correct
13 Execution timed out 5043 ms 106044 KB Time limit exceeded
14 Halted 0 ms 0 KB -