글 읽기 - 30퍼에서 시간초과가 나는 이유를 모르겠습니다.

qktlf789456 3년 전 0

혹시 이분탐색일려나요 .. ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define EMPTY -1235651


/*
5
1500 1500
-17000 4500
1200 5700
-5600 100
-200 9900
*/

int size;

long long* data;
int data_size = 0;

long long* remain_data;
long long remain_size = 0;
long long min_remain = 999999999999999999;


long long abs(long long data)
{
	return data < 0 ? data * -1 : data;
}

int main()
{
	long long value, current = 0, remain;

	scanf("%d", &size);

	data = (long long*)malloc(sizeof(long long) * size);
	remain_data = (long long*)malloc(sizeof(long long) * size);
	



	long long min_value = 999999999999999999;
	for (int i = 0; i < size; i++)
	{
		scanf("%lld", &value);
		scanf("%lld", &remain);


		if (value < 0 && abs(value) > current)
		{
			long long newvalue = (value + current) * -1 + remain;

			data[data_size++] = newvalue;


			if (min_value > data[data_size - 1])
				min_value = data[data_size - 1];



			if (newvalue > remain)
			{
				remain_data[remain_size++] = remain;

				if (remain < min_remain)
					min_remain = remain;
			}


			current = remain;
		}
		else
		{
			//입력모순검사
			current += value;

			if (current != remain)
			{
				//입력모순
				printf("-1");
				return 0;
			}


		}


	}

	
	/*
	for (int i = 0; i < data_size; i++)
		printf("[%lld]", data[i]);
	*/


	//M의 값을 정할필요가 없을경우
	if (data_size == 0)
	{
		printf("1");
		return 0;
	}

	//M이 단 하나 발견됬을 경우
	if (data_size == 1)
	{
		printf("%lld", data[0]);
		return 0;
	}

	long long result = min_remain+1;
	for (; result <= min_value; result++)
	{
		for (int i = 0; i < data_size; i++)
		{
			if (data[i] % result != 0)
				break;

			if (i == data_size - 1)
			{




				for (int j = 0; j < remain_size; j++)
				{
					if (remain_data[j] >= result)
						break;

					if (j == remain_size - 1)
					{
						printf("%lld", result);
						return 0;
					}
				}
			}

		}





	}

	printf("-1");

	return 0;
}

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

문제

문제

출처

ICPC

30퍼에서 시간초과가 나는 이유를 모르겠습니다.

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말