oj.uz

Submission #431552

# Submission time Handle Problem Language Result Execution time Memory
431552 2021-06-17T12:56:05 Z APROHACK Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 105996 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 4 ms 1608 KB Output is correct
6 Correct 4 ms 1608 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 4 ms 1608 KB Output is correct
6 Correct 4 ms 1608 KB Output is correct
7 Correct 23 ms 4964 KB Output is correct
8 Correct 22 ms 4972 KB Output is correct
9 Correct 23 ms 4788 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 4 ms 1608 KB Output is correct
6 Correct 4 ms 1608 KB Output is correct
7 Correct 23 ms 4964 KB Output is correct
8 Correct 22 ms 4972 KB Output is correct
9 Correct 23 ms 4788 KB Output is correct
10 Correct 373 ms 24064 KB Output is correct
11 Correct 396 ms 24060 KB Output is correct
12 Correct 178 ms 18164 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 4 ms 1608 KB Output is correct
6 Correct 4 ms 1608 KB Output is correct
7 Correct 23 ms 4964 KB Output is correct
8 Correct 22 ms 4972 KB Output is correct
9 Correct 23 ms 4788 KB Output is correct
10 Correct 373 ms 24064 KB Output is correct
11 Correct 396 ms 24060 KB Output is correct
12 Correct 178 ms 18164 KB Output is correct
13 Execution timed out 5024 ms 105996 KB Time limit exceeded
14 Halted 0 ms 0 KB -