아직 계정이 없으신가요? 회원가입

Dev. Talk

수퍼컴퓨터 클러스터 문제 시간 초과의 원인을 모르겠습니다

회원사진leekb123
12 views2022-11-24 19:09

#include <iostream>
#include <vector>

using namespace std;

int vCom[100001];

typedef long long ll;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	ll B;

	cin >> n >> B;

	for ( int i = 0 ; i < n ; ++i )
	{
		cin >> vCom[i];
	}

	ll answer = 0;

	int temp;
	int min = 0;
	int max = 2000000000;

	while(min <= max)
	{
		int mid = (max + min) / 2;
		
		ll cost = 0;

		bool bPossible = true;

		for ( int i = 0 ; i < n ; ++i )
		{
			if ( mid < vCom[i] )
			{
				continue;
			}

			temp = mid - vCom[i];

			cost += (ll)temp * (ll)temp;

			if ( B < cost )
			{
				bPossible = false;
				break;
			}	
		}

		if ( !bPossible )
		{
			max = mid - 1;
		}

		else
		{
			min = mid + 1;
			answer = mid;
		}
	}

	cout << answer << endl;

	return 0;
}


대부분의 case 는 문제 없이 수십 ms 이하로 잘 동작하는데 

특정 4개 케이스는 이상하게 3000ms 이상 시간이 걸려서 최종적으로 실패합니다

코드 상에서 별다른 문제점을 찾지 못했는데

혹시 원인을 알 수 있을까 싶어서 글을 올립니다

도와주세요ㅜㅜ