Submission #3814197

---

Source Code Expand

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

int main () {
    ll n;
    cin >> n;
    ll h[n], s[n];
    ll last[n];
    for (ll i = 0; i < n; i++) {
        cin >> h[i] >> s[i];
        last[i] = h[i] + s[i] * (n - 1);
    }
    sort(last, last + n);
    ll left = -1;
    ll right = last[n - 1] + 1;
    ll mid;
    while (left < right - 1) {
        mid = (left + right) / 2;
        ll itr[n], sum[n];
        for (ll i = 0; i < n; i++) {
            sum[i] = 0;
            itr[i] = 0;
        }    
        bool none = false;
        for (ll i = 0; i < n; i++) {
            if (mid < h[i]) {
                none = true;
                break;
            }
            else {
                ll sub = (mid - h[i]) / s[i];
                itr[sub]++;
            }
        }
        for (ll i = 0; i < n; i++) {
            if (i != 0) {
                sum[i] = sum[i - 1] + itr[i];
            }
            else {
                sum[i] = itr[i];
            }
            if (sum[i] > i + 1) {
                none = true;
                break;
            }
        }
        if (none) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    cout << right << endl;
}

Submission Info

Judge Result