oj.uz

Submission #431461

# Submission time Handle Problem Language Result Execution time Memory
431461 2021-06-17T12:01:42 Z APROHACK Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 105988 KB 
#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(check(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(check(i))pos=i;
	}
	return pos;
}

Compilation message

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

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 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 640 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 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 37 ms 4972 KB Output is correct
8 Correct 37 ms 4896 KB Output is correct
9 Correct 25 ms 4872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 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 37 ms 4972 KB Output is correct
8 Correct 37 ms 4896 KB Output is correct
9 Correct 25 ms 4872 KB Output is correct
10 Correct 568 ms 24048 KB Output is correct
11 Correct 407 ms 24048 KB Output is correct
12 Correct 226 ms 18148 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 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 37 ms 4972 KB Output is correct
8 Correct 37 ms 4896 KB Output is correct
9 Correct 25 ms 4872 KB Output is correct
10 Correct 568 ms 24048 KB Output is correct
11 Correct 407 ms 24048 KB Output is correct
12 Correct 226 ms 18148 KB Output is correct
13 Execution timed out 5015 ms 105988 KB Time limit exceeded
14 Halted 0 ms 0 KB -