Submission #1277190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277190		shirokito	Self Study (JOI22_ho_t2)	C++20	100 / 100	235 ms	5132 KiB

Main

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

using ll = long long;

const int N = 3e5 + 24;
const ll INF = 1e18;

ll n, m, a[N], b[N];

void solve() {
    cin >> n >> m;

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

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

    ll res = INF;

    for (ll l = 1, r = INF; l <= r; ) {
        ll mid = (l + r) / 2;
        ll s = 0; bool flag = 0;

        for (int i = 1; i <= n; i++) {
            if (a[i] * m >= mid) {
                if (b[i] >= a[i]) {
                    ll add = m - (mid + b[i] - 1) / b[i];
                    s += add;
                }
                else {
                    ll add = m - (mid + a[i] - 1) / a[i];
                    s += add;
                }
            }
            else if (b[i] * m >= mid) {
                ll add = m - (mid + b[i] - 1) / b[i];
                s += add;
            }
        }   

        for (int i = 1; i <= n; i++) {
            if (a[i] * m < mid) {
                if (b[i] * m >= mid) continue;
                ll need = (mid - max(b[i], a[i]) * m + b[i] - 1) / (b[i]);
                if (s < need) { flag = 1; break; }
                s -= need;
            }
        }

        if (!flag) res = mid, l = mid + 1;
        else r = mid - 1;
    }

    cout << res << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(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