Submission #928173

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 1000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

const LL MAXVAL = 1LL * INF * INF + INF;

int n; LL t, a;

int main() {
    GI(n); LL rest, resa;

    GLL(rest); GLL(resa);

    FORN(i, n-1) {
        GLL(t); GLL(a);
        
        LL lo = 1; LL hi = MAXVAL / max(a, t); LL res = -1;

        while (lo <= hi) {
            LL mid = (lo + hi) / 2;

            if (mid * t >= rest && mid * a >= resa) {
                res = mid;
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }

        rest = res * t;
        resa = res * a;
    }

    cout << rest + resa << "\n";
    return 0;
}

Submission Info

Judge Result