Submission #19065031

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int64_t calc_lower_bound(int N, const vector<int64_t> &H_vec)
{
    int64_t lower = 0;
    for (int i = 0; i < N; ++i) {
        int64_t lower_i = H_vec.at(i);
        if (lower < lower_i)
            lower = lower_i;
    }
    return lower;
}

int64_t calc_upper_bound(int N, const vector<int64_t> &H_vec,
        const vector<int64_t> &S_vec)
{
    int64_t upper = 0;
    for (int i = 0; i < N; ++i) {
        int64_t upper_i = H_vec.at(i) + S_vec.at(i) * (N - 1);
        if (upper < upper_i)
            upper = upper_i;
    }
    return upper;
}

bool is_feasible(int N, const vector<int64_t> &H_vec,
        const vector<int64_t> &S_vec, int64_t score)
{
    vector<int64_t> limit_vec(N);
    for (int i = 0; i < N; ++i) {
        int64_t diff = score - H_vec.at(i);
        if (diff < 0)
            return false;
        int64_t limit = diff / S_vec.at(i);
        limit_vec.at(i) = limit;
    }
    sort(limit_vec.begin(), limit_vec.end());
    for (int i = 0; i < N; ++i) {
        if (limit_vec.at(i) < i)
            return false;
    }
    return true;
}

int main()
{
    int N;
    cin >> N;
    vector<int64_t> H_vec(N), S_vec(N);
    for (int i = 0; i < N; ++i) 
        cin >> H_vec.at(i) >> S_vec.at(i);
    int64_t ok = calc_upper_bound(N, H_vec, S_vec);
    int64_t ng = calc_lower_bound(N, H_vec) - 1;
    while (abs(ok - ng) > 1) {
        int64_t mid = (ok + ng) / 2;
        if (is_feasible(N, H_vec, S_vec, mid))
            ok = mid;
        else
            ng = mid;
    }
    cout << ok<< endl;
}

Submission Info

Judge Result