Submission #1196515

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

Main

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define vi vector<int>
#define int long long

int ceil(int a, int b) {
    return (a + b - 1) / b;
}

bool is_possible(int x, const vector<int>& a, const vector<int>& b, const vector<int>& enum_order, int m) {
    int extra = 0;
    for (int i : enum_order) {
        int p;
        if (b[i] >= a[i]) p = b[i];
        else p = a[i];

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;
    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])) || (max(a[i], b[i]) == max(a[j], b[j]) && min(a[i], b[i]) > min(a[j], b[j]));
    });
    
    int l = 0, r = INT64_MAX;
    while (r-l>1) {
        int mid = (l+r)/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