Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
1.4 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>

long long maxInvitedFriends(int pivotStart, int pivotEnd, int maxFriends, const std::vector<std::pair<int, long long>>& zipped, int nf, long long nm) {
    int pivot = (pivotStart + pivotEnd) / 2;
    long long min = 0;
    for (int i = 0; i < pivot; ++i) {
        min += zipped[i].first + (pivot - 1) * zipped[i].second;
    }

    if (min <= nm) {
        if (pivot < pivotEnd)
            return maxInvitedFriends(pivot + 1, pivotEnd, pivot, zipped, nf, nm);
        else
            return pivot;
    } else {
        if (pivot > pivotStart)
            return maxInvitedFriends(pivotStart, pivot - 1, maxFriends, zipped, nf, nm);
        else
            return maxFriends;
    }
}

int main() {
    int nf;
    long long nm;
    std::cin >> nf >> nm;
    std::vector<int> appetite(nf);
    std::vector<long long> happiness(nf);
    for (int i = 0; i < nf; ++i) {
        std::cin >> appetite[i];
    }
    for (int i = 0; i < nf; ++i) {
        std::cin >> happiness[i];
    }

    std::vector<std::pair<int, long long>> zipped;
    for (int i = 0; i < nf; ++i) {
        zipped.emplace_back(appetite[i], happiness[i]);
    }
    std::sort(zipped.begin(), zipped.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    std::cout << maxInvitedFriends(1, nf, 0, zipped, nf, nm) << std::endl;

    return 0;
}