BOJ 2180번: 소방서의 고민

https://www.acmicpc.net/problem/2180

2180번: 소방서의 고민

a가 제일 큰 화재부터 먼저 진압하고, a가 같은 경우에는 b가 작은 화재부터 먼저 진압한다..

예제도 모두 맞는데, 시간초과가 난다....

c++로 갈아탄 후에는 틀렸습니다. 가 나오는 걸로 봐서는 이렇게 풀면 안되나 보다.. 내가 c++을 잘 몰라서 틀린 걸 수도.. 아무튼 수식으로 정리를 해서 풀었다.. b/a < d/c 로 했더니 또 틀렸습니다.. 나와서 곱셈으로 바꿔서 했더니 맞단다... 왜그럴까....

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<pair<int, int>> arr;

bool comp(pair<int, int> A, pair<int, int> B)
{
	int a = A.first, b = A.second, c = B.first, d = B.second;
	if (a==0){
	    return false;
	}
	else if (c==0){
	    return true;
	}
	else if (b==0 && d==0){
	    return a < c;
	}
	return  b * c < a * d;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int a, b;

	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		arr.push_back(make_pair(a,b));
	}

	sort(arr.begin(), arr.end(), comp);
	long long ans = 0;

	for (int i = 0; i < arr.size(); i++)
	{
        ans += arr[i].first * ans + arr[i].second;
		ans %= 40000;
	}
	cout << ans;
	return 0;
}