oj.uz

Submission #431510

# Submission time Handle Problem Language Result Execution time Memory
431510 2021-06-17T12:32:09 Z APROHACK Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 106032 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(sumar(0, j, 0-Hg, 0-Wg)>0)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)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 'bool check(int)':
quality.cpp:32:11: warning: statement has no effect [-Wunused-value]
   32 |   sum[0][j];
      |   ~~~~~~~~^
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:46:6: warning: unused variable 'minimum' [-Wunused-variable]
   46 |  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 1616 KB Output is correct
5 Correct 4 ms 1560 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 1616 KB Output is correct
5 Correct 4 ms 1560 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 32 ms 4952 KB Output is correct
9 Correct 24 ms 4876 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 1616 KB Output is correct
5 Correct 4 ms 1560 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 32 ms 4952 KB Output is correct
9 Correct 24 ms 4876 KB Output is correct
10 Correct 477 ms 24056 KB Output is correct
11 Correct 352 ms 24056 KB Output is correct
12 Correct 214 ms 18152 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 1616 KB Output is correct
5 Correct 4 ms 1560 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 24 ms 4940 KB Output is correct
8 Correct 32 ms 4952 KB Output is correct
9 Correct 24 ms 4876 KB Output is correct
10 Correct 477 ms 24056 KB Output is correct
11 Correct 352 ms 24056 KB Output is correct
12 Correct 214 ms 18152 KB Output is correct
13 Execution timed out 5029 ms 106032 KB Time limit exceeded
14 Halted 0 ms 0 KB -