## Intuition The problem requires maximizing the score after performing a limited number of operations on two arrays, `a` and `b`. Each operation involves selecting an index `i`, adding `a[i]` to the score, and then reducing `a[i]` by `b[i]`. The challenge is to choose the sequence of operations that yields the highest score within the given constraints. The key insight is to use a greedy approach: always choose the operation that provides the maximum immediate benefit. This involves considering both the current value of `a[i]` and the rate at which it decreases (`b[i]`). We need to prioritize indices where the value of `a[i]` remains high for as many operations as possible. ## Approach 1. **Binary Search on Operations**: For each test case, determine the maximum score achievable with exactly `k` operations. Since `k` can be very large, we need an efficient way to simulate operations. 2. **Greedy Selection**: Use a max-heap (priority queue) to always select the index `i` with the highest current `a[i]` value for each operation. After selecting `i`, update `a[i]` to `max(0, a[i] - b[i])`. 3. **Simulate Operations**: Perform up to `k` operations by repeatedly extracting the maximum from the heap, updating the score, and pushing the updated value back into the heap if it's greater than zero. 4. **Output the Result**: After simulating the operations for each test case, output the maximum score obtained. ## Complexity - **Time Complexity**: O(n log n) per test case due to the use of a max-heap for selecting operations. This is efficient given the constraints. - **Space Complexity**: O(n) for storing the heap. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; long long k; cin >> n >> k; vector a(n), b(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < n; ++i) { cin >> b[i]; } // Max-heap to store pairs of (-a[i], i) for easy max extraction priority_queue> pq; for (int i = 0; i < n; ++i) { pq.push({a[i], i}); } long long max_score = 0; while (k-- > 0 && !pq.empty()) { auto [current_a, idx] = pq.top(); pq.pop(); if (current_a <= 0) break; // If the max value is zero or less, stop max_score += current_a; a[idx] = max(0LL, a[idx] - b[idx]); if (a[idx] > 0) { pq.push({a[idx], idx}); } } cout << max_score << '\n'; } return 0; } ``` This solution efficiently manages the operations using a priority queue to always select the most beneficial operation, ensuring that the maximum score is achieved within the given constraints.

Bomb

Problem Details