글 읽기 - 간단하게 생각했는데.. 여기 반례가 있을까요?

wyldecat 8년 전 1

계속 해봐도 틀리는구만요..

각 x구간의 y값의 min값과 max값을 배열에 저장하였습니다.

그다음 모든 좌표상의 x를 탐색하면서,

그 x를 시작점으로 했을때.. 가질 수 있는 모든 y의 시작점과 끝점에 대해 가질 수 있는 직사각형의 최대 넓이를 계산했습니다.

좀 느리긴해도 TLE는 안뜰것같아서 풀어보는데, TLE는 커녕 틀렸습니다가 나오네요 ㅠㅠ

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>

using namespace std;

int main()
{
	
	int MAX[115] = { 0, }, MIN[116],k,x,y;

	for (int i = 0; i <= 115; i++) MIN[i] = 999;

	scanf("%d", &k);
	for (int i = 0; i < k; i++)
	{
		scanf("%d %d", &x, &y);

		for (int j = x; j <= x + 10; j++)
		{
			if (MAX[j] < y + 10) MAX[j] = y + 10;
			if (MIN[j] > y) MIN[j] = y;
		}

	}

	int answer = 0;

	for (int i = 0; i <=100; i++)
	{
		for (int y1 = MIN[i]; y1 <= MAX[i]; y1++)
		{
			for (int y2 = y1 + 1; y2 <= MAX[i]; y2++)
			{
				for (int l = i + 1; l <= 101; l++)
				{
					if (y1<MIN[l] || y2>MAX[l]) break;
					answer = max(answer, (l - i)*(y2 - y1));
				}
			}
		}
		
	}
	printf("%d\n", answer);
	return 0;
}

wyldecat 8년 전 1

아이구야.. 2번문제라구 후딱 생각했는데.. 오류 투성이네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

간단하게 생각했는데.. 여기 반례가 있을까요?

wyldecat 8년 전 1

wyldecat 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말