Submission #921494

#	Time	Username	Problem	Language	Result	Execution time	Memory
921494		cthbst	Self Study (JOI22_ho_t2)	C++14	100 / 100	203 ms	5384 KiB

Main

#include <algorithm>
#include <iostream>

#define int long long

using namespace std;

const int MAXN = 300005;

int n, m;
int a[MAXN];
int b[MAXN];

void init() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    for (int i = 0; i < n; i++) a[i] = max(a[i], b[i]);
}

int div_ceil(int x, int y) {
    int ans = x / y;
    if (x % y > 0) ans++;
    return ans;
}

bool check(int D) {
    //  __int128 extra = 0;
    int extra = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] * m >= D) {
            int val = m - div_ceil(D, a[i]);
            extra += val;
        } else {  // a[i] * m < D
            int val = div_ceil(D - a[i] * m, b[i]);
            extra -= val;
            if (extra < -n * m) return false;
        }
    }
    return extra >= 0;
}

void solve() {
    int l = 1;
    int r = 1 + (int)1e18;

    // check(D) : D 愈小愈容易
    while (l != r) {
        int mid = (l + r) / 2;
        if (check(mid) == false) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    int ans = r - 1;
    cout << ans << '\n';
}

signed main() {
    cin.tie(0);
    cin.sync_with_stdio(0);

    init();
    solve();

    return 0;
}

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