Submission #1196512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196512		ofoz	Self Study (JOI22_ho_t2)	C++20	62 / 100	106 ms	16300 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define vi vector<int>
#define int unsigned 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<pi> sorting;
    for (int i = 0; i < n; i++) { sorting.push_back({max(a[i], b[i]), i}); }
    sort(sorting.begin(), sorting.end());
    reverse(sorting.begin(), sorting.end());
    vector<int> indices;
    for (pi p : sorting) { indices.push_back(p.second); }
    
    int l = 0, r = UINT64_MAX;
    while (r-l>1) {
        int mid = (l+r)/2;
        if (is_possible(mid, a, b, indices, 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