Untitled
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; }