Tap here to switch tabs
Problem
Submissions

Problem: Maximum Total from Optimal Activation Order

Try to solve the Maximum Total from Optimal Activation Order problem.

Statement

You are given two integer arrays value and limit, both of length n.

There are n elements indexed from 00 to n−1n - 1. Initially, all elements are available, and no element is active.

You can activate available elements one by one in any order. In each step, you select an available element i and perform the following actions:

  1. Add value[i] to the total sum.

  2. Add element i to the set of active elements.

  3. Let k be the total number of currently active elements. Every element j satisfying limit[j] ≤k\leq k becomes inactive, whether it was currently active or available. Inactive elements can never be activated in future steps, and any active element that becomes inactive is removed from the active set.

The process stops when there are no more available elements to activate.

Return the maximum total sum that can be obtained from an optimal activation order.

Constraints:

  • 1≤n==1 \leq n == value.length ==== limit.length ≤105\leq 10^5

  • 1≤1 \leq value[i] ≤105\leq 10^5

  • 1≤1 \leq limit[i] ≤n\leq n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Total from Optimal Activation Order

Try to solve the Maximum Total from Optimal Activation Order problem.

Statement

You are given two integer arrays value and limit, both of length n.

There are n elements indexed from 00 to n−1n - 1. Initially, all elements are available, and no element is active.

You can activate available elements one by one in any order. In each step, you select an available element i and perform the following actions:

  1. Add value[i] to the total sum.

  2. Add element i to the set of active elements.

  3. Let k be the total number of currently active elements. Every element j satisfying limit[j] ≤k\leq k becomes inactive, whether it was currently active or available. Inactive elements can never be activated in future steps, and any active element that becomes inactive is removed from the active set.

The process stops when there are no more available elements to activate.

Return the maximum total sum that can be obtained from an optimal activation order.

Constraints:

  • 1≤n==1 \leq n == value.length ==== limit.length ≤105\leq 10^5

  • 1≤1 \leq value[i] ≤105\leq 10^5

  • 1≤1 \leq limit[i] ≤n\leq n