Submission #526483

#	Time	Username	Problem	Language	Result	Execution time	Memory
526483		PurpleCrayon	Self Study (JOI22_ho_t2)	C++17	100 / 100	367 ms	9680 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 2e5+10, MOD = 1e9+7;
const ll INF = (long long)1e18+10;

void solve() {
    // a[i] := max(a[i], b[i])
    // binary search, take the minimum number of a's such that I'm satisfied

    int n; ll m; cin >> n >> m;
    vector<ll> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    for (int i = 0; i < n; i++) a[i] = max(a[i], b[i]);

    auto v = [&](ll x) -> bool {
        __int128 has = 0;
        for (int i = 0; i < n; i++) {
            ll need = (x + a[i] - 1) / a[i];
            if (need <= m) has += m - need;
            else has -= (x - a[i] * m + b[i] - 1) / b[i];
        }
        return has >= 0;
    };

    ll lo = 0, hi = INF, mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (v(mid)) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }
    cout << lo << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9