oj.uz

답안 #431424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431424 2021-06-17T11:50:47 Z APROHACK 삶의 질 (IOI10_quality) C++14
80 / 100
 5000 ms 175380 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(a[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(dou)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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 1620 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1632 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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 1620 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1632 KB Output is correct
7 Correct 24 ms 5500 KB Output is correct
8 Correct 24 ms 5388 KB Output is correct
9 Correct 25 ms 5240 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 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 1620 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1632 KB Output is correct
7 Correct 24 ms 5500 KB Output is correct
8 Correct 24 ms 5388 KB Output is correct
9 Correct 25 ms 5240 KB Output is correct
10 Correct 405 ms 30796 KB Output is correct
11 Correct 383 ms 30792 KB Output is correct
12 Correct 164 ms 21436 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 1620 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1632 KB Output is correct
7 Correct 24 ms 5500 KB Output is correct
8 Correct 24 ms 5388 KB Output is correct
9 Correct 25 ms 5240 KB Output is correct
10 Correct 405 ms 30796 KB Output is correct
11 Correct 383 ms 30792 KB Output is correct
12 Correct 164 ms 21436 KB Output is correct
13 Correct 4900 ms 175380 KB Output is correct
14 Execution timed out 5053 ms 175380 KB Time limit exceeded
15 Halted 0 ms 0 KB -