Submission #8159504


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> as(n), fs(n);
    for (auto& a : as) {
        cin >> a;
    }
    for (auto& f : fs) {
        cin >> f;
    }
    sort(as.begin(), as.end(), [&](auto& i, auto& j) { return i > j; });
    sort(fs.begin(), fs.end());
    long long lo = -1, hi = as[0] * fs.back();
    // lo impossible, hi possible.
    while (hi - lo > 1) {
        long long mid = (hi + lo)/2;
        long long required = 0;
        for (int i = 0; i < n; ++i) {
            // (a-k)*f <= mid <=> a-k <= floor(mid/f) <=> k >= a - floor(mid/f)
            required += max(0LL, as[i] - (mid/fs[i]));
        }
        if (required <= k) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << hi << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Gluttony
User Tejs
Language C++14 (GCC 5.4.1)
Score 500
Code Size 939 Byte
Status
Exec Time 140 ms
Memory 3456 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 500 / 500 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_01.txt 120 ms 3456 KB
sub1_02.txt 3 ms 384 KB
sub1_03.txt 43 ms 1408 KB
sub1_04.txt 11 ms 512 KB
sub1_05.txt 63 ms 1664 KB
sub1_06.txt 81 ms 2176 KB
sub1_07.txt 2 ms 256 KB
sub1_08.txt 112 ms 2816 KB
sub1_09.txt 40 ms 1152 KB
sub1_10.txt 68 ms 1792 KB
sub1_11.txt 87 ms 2176 KB
sub1_12.txt 37 ms 1152 KB
sub1_13.txt 18 ms 640 KB
sub1_14.txt 61 ms 1792 KB
sub1_15.txt 49 ms 1408 KB
sub1_16.txt 78 ms 2048 KB
sub1_17.txt 63 ms 1664 KB
sub1_18.txt 117 ms 3328 KB
sub1_19.txt 117 ms 3456 KB
sub1_20.txt 117 ms 3456 KB
sub1_21.txt 117 ms 3456 KB
sub1_22.txt 117 ms 3456 KB
sub1_23.txt 115 ms 3456 KB
sub1_24.txt 117 ms 3456 KB
sub1_25.txt 118 ms 3456 KB
sub1_26.txt 139 ms 3456 KB
sub1_27.txt 138 ms 3328 KB
sub1_28.txt 139 ms 3328 KB
sub1_29.txt 137 ms 3328 KB
sub1_30.txt 140 ms 3328 KB
sub1_31.txt 139 ms 3328 KB
sub1_32.txt 139 ms 3456 KB
sub1_33.txt 139 ms 3328 KB
sub1_34.txt 3 ms 256 KB
sub1_35.txt 65 ms 1792 KB