소방서의 고민 (JUNGOL 6276)

https://jungol.co.kr/problem/6276?cursor=MTIsMCwy

---

아이디어

Exchange Argument를 사용하면 b/a의 값이 증가하는 순서대로 배열하는것이 최적임을 알 수 있습니다. 하지만 이때 a와 b의 값이 0일때에는 따로 처리를 해주어야합니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

bool cmp(pair <ll,ll> A,pair <ll,ll> B)
{
    if (A.first==0 && A.second==0) return false;
    if (B.first==0 && B.second==0) return true;
    if (A.first || B.first) return A.first*B.second>B.first*A.second; 
    return A.second>B.second;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,a,b,t=0;
    vector <pair <ll,ll> > v;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>a>>b;
        v.push_back({a,b});
    }

    sort (v.begin(),v.end(),cmp);

    for (i=0;i<N;i++)
    {
        t+=v[i].first*t+v[i].second;
        t%=40000;
    }

    cout<<t;
}