Problem Info
H - Two Pointers Method - Codeforces
My Work
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using std::cout;
using std::endl;
using std::vector;
using std::map;
long long max_pair(
const map<long long, long long>& first,
const map<long long, long long>& second,
int limit
) {
auto second_at = second.rbegin();
long long val = 0;
for (auto first_at = first.begin(); first_at != first.end(); first_at++) {
// think deref-ing iterators takes a long time
int first_val = first_at->first;
// use binary search to determine the most of second we can squeeze in first
auto most_second = second.upper_bound(limit - first_val);
if (most_second == second.begin()) {
val = std::max(val, first_at->second);
continue;
}
most_second--;
val = std::max(val, first_at->second + most_second->second);
}
return val;
}
int main() {
int a_amt;
int b_amt;
int max_weight;
int a_weight;
int b_weight;
std::cin >> a_amt >> b_amt >> max_weight >> a_weight >> b_weight;
vector<int> a_items(a_amt);
for (int& a : a_items) {
std::cin >> a;
}
std::sort(a_items.begin(), a_items.end(), std::greater<int>());
vector<int> b_items(b_amt);
for (int& b : b_items) {
std::cin >> b;
}
std::sort(b_items.begin(), b_items.end(), std::greater<int>());
// a_best and b_best contain a mapping of a weight
// to the best achievable cost using exactly that weight
map<long long, long long> a_best;
long long curr_weight = 0;
long long curr_val = 0;
for (int a : a_items) {
curr_weight += a_weight;
curr_val += a;
if (curr_weight > max_weight) {
break;
}
a_best[curr_weight] = curr_val;
}
map<long long, long long> b_best;
curr_weight = 0;
curr_val = 0;
for (int b : b_items) {
curr_weight += b_weight;
curr_val += b;
if (curr_weight > max_weight) {
break;
}
b_best[curr_weight] = curr_val;
}
cout << max_pair(a_best, b_best, max_weight) << endl;
}
I’ve also tried this implementation here, but neither of them work. Could I know what’s wrong with my code or a test case that fails it?