Submission #1092638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092638		ortsac	Self Study (JOI22_ho_t2)	C++17	100 / 100	277 ms	13916 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 3e5 + 10;
int a[MAXN], b[MAXN];
int n, m;

bool check(int x) {
    int rem = 0;
    vector<int> need(n);
    for (int i = 0; i < n; i++) {
        int qtd = ((x + a[i] - 1)/a[i]);
        if (qtd > m) need[i] = (x - m*a[i]);
        else rem += (m - qtd);
    }
    for (int i = 0; i < n; i++) {
        int qtd = ((need[i] + b[i] - 1)/b[i]);
        rem -= qtd;
        if (rem < 0) return 0;
    }
    return 1;
}

int32_t main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        a[i] = max(a[i], b[i]);
    }
    int l = 0, r = 1e18, ans;
    while (l <= r) {
        int m = (l+r)/2;
        if (check(m)) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << ans << "\n";
}

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