Submission #895407

#	Time	Username	Problem	Language	Result	Execution time	Memory
895407		juliany2	Self Study (JOI22_ho_t2)	C++17	100 / 100	272 ms	11592 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 3e5 + 7;
int n;
ll m, a[N], b[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    ll lo = 1, hi = 1e18;
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;

        ll need = 0;
        for (int i = 1; i <= n; i++) {
            if (b[i] >= a[i])
                need += (mid + b[i] - 1) / b[i];
            else {
                ll take = min(m, (mid + a[i] - 1) / a[i]);
                need += take + (max(mid - take * a[i], 0LL) + b[i] - 1) / b[i];
            }

            if (need > m * n)
                break;
        }

        if (need <= m * n)
            lo = mid;
        else
            hi = mid - 1;
    }

    cout << lo << '\n';

    return 0;
}

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