Submission #1196509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196509		ofoz	Self Study (JOI22_ho_t2)	C++20	62 / 100	117 ms	7492 KiB

Main

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

bool is_possible(int x, const vector<int>& a, const vector<int>& b, const vector<int>& enum_order, int m) {
    int extra = 0;
    int n = a.size();

    for (int i : enum_order) {
        int p = max(a[i], b[i]);
        if (b[i] >= a[i]) p = b[i];
        else p = a[i];

        int op = (x + p - 1) / p; // ceil(x / p)
        if (op <= m) {
            extra += (m - op);
            continue;
        }
        assert(x >= m * p);
        int needed = min(x - m * p, extra * (int)b[i]);
        op = (x - needed + p - 1) / p;
        if (op > m) return false;

        extra -= (needed + b[i] - 1) / b[i];
    }

    return true;
}

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

    vector<int> a(n), b(n);
    for (int& ai : a) cin >> ai;
    for (int& bi : b) cin >> bi;

    vector<int> enum_order(n);
    for (int i = 0; i < n; ++i) enum_order[i] = i;

    sort(enum_order.begin(), enum_order.end(), [&](int i, int j) {
        return max(a[i], b[i]) > max(a[j], b[j]);
    });

    int l = 0, r = numeric_limits<int>::max();
    while (r - l > 1) {
        int mid = l + (r - l) / 2;
        if (is_possible(mid, a, b, enum_order, m))
            l = mid;
        else
            r = mid;
    }

    cout << l << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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