Imagine a game where you play as a character that has two attributes: "Strength" and…
- User
Imagine a game where you play as a character that has two attributes: "Strength" and "Intelligence", that are at zero level initially.
During the game, you'll acquire 𝑚 attribute points that allow you to increase your attribute levels — one point will increase one of the attributes by one level. But sometimes, you'll encounter a so-called "Attribute Checks": if your corresponding attribute is high enough, you'll pass it; otherwise, you'll fail it.
Spending some time, you finally prepared a list which contains records of all points you got and all checks you've met. And now you're wondering: what is the maximum number of attribute checks you can pass in a single run if you'd spend points wisely?
Note that you can't change the order of records.
Input The first line contains two integers 𝑛 and 𝑚 (1≤𝑚≤5000; 𝑚<𝑛≤2⋅106) — the number of records in the list and the total number of points you'll get during the game.
The second line contains 𝑛 integers 𝑟1,𝑟2,…,𝑟𝑛 (−𝑚≤𝑟𝑖≤𝑚), where 𝑟𝑖 encodes the 𝑖-th record:
If 𝑟𝑖=0, then the 𝑖-th record is an acquiring one attribute point. You can spend to level up either Strength or Intelligence; If 𝑟𝑖>0, then it's an Intelligence check: if your Intelligence level is greater than or equal to |𝑟𝑖|, you pass. If 𝑟𝑖<0, then it's a Strength check: if your Strength level is greater than or equal to |𝑟𝑖|, you pass. Additional constraint on the input: the sequence 𝑟1,𝑟2,…,𝑟𝑛 contains exactly 𝑚 elements equal to 0.
Output Print one integer — the maximum number of checks you can pass.
Examples inputCopy 10 5 0 1 0 2 0 -3 0 -4 0 -5 outputCopy 3 inputCopy 3 1 1 -1 0 outputCopy 0 inputCopy 9 3 0 0 1 0 2 -3 -2 -2 1 outputCopy 4 Note In the first test, it's optimal to spend each point in Strength, so you'll fail 2 Intelligence checks but pass 3 Strength checks.
In the second test, you'll fail both checks, since the first point you get comes after the checks.
In the third test, one of the optimal strategies is:
spend the first point on Intelligence; spend the second point on Strength; spend the third point on Strength; As a result, you'll pass 2 Intelligence checks 𝑟3 and 𝑟9 and 2 Strength checks 𝑟7 and 𝑟8.
- Assistant
To solve this problem, we need to maximize the number of attribute checks passed by strategically allocating attribute points to either "Strength" or "Intelligence." Here’s a step-by-step breakdown of how to approach this:
Step 1: Understanding the Problem
- You have
nrecords in the order you encounter them. - Out of these
nrecords, exactlymare allocations (r_i = 0), and the remainingn-mare checks. - An allocation point can be assigned to either Strength or Intelligence.
- For each check, you pass if the corresponding attribute meets the required level.
Step 2: Splitting Records into Segments
- Split the
nrecords intom+1segments. Each segment contains the checks that occur between two allocations. - The first segment (segment 0) is before the first allocation.
- The last segment (segment
m) is after the last allocation.
Step 3: Sorting Checks Within Each Segment
- For each segment, separate the Strength and Intelligence checks.
- Sort these checks in ascending order. This allows us to efficiently count how many checks can be passed given a certain allocation.
Step 4: Dynamic Programming (DP) Approach
- Use a DP table where
dp[i][s]represents the maximum number of checks passed after allocatingipoints, withspoints allocated to Strength. - Initialize the DP table with
dp[0][0] = 0(no allocations means no checks passed). - For each segment, update the DP table by deciding whether to allocate the next point to Strength or Intelligence.
- For each allocation decision:
- Calculate how many checks in the current segment can be passed with the current allocation.
- Update the DP entries based on whether you allocate to Strength or Intelligence.
Step 5: Implement the Solution Efficiently
- Given the constraints (
n <= 2 * 10^6andm <= 5000), ensure that the solution is optimized to run within acceptable time limits. - Use binary search (
bisect) to efficiently count the number of checks that can be passed in each segment based on the current allocation.
Step 6: Extract the Final Answer
- After processing all segments and allocations, the answer is the maximum value found in the DP table.
Example Walkthrough
Let's take the first sample input:
10 5 0 1 0 2 0 -3 0 -4 0 -5-
Segments:
- Segment 0: []
- Segment 1: [1]
- Segment 2: [2]
- Segment 3: [-3]
- Segment 4: [-4]
- Segment 5: [-5]
-
Optimal Allocation:
- Allocate all points to Strength, passing checks
-3,-4, and-5.
- Allocate all points to Strength, passing checks
Implementation
Here's the Python code implementing the above strategy:
import sys import threading import bisect def main(): import sys sys.setrecursionlimit(1 << 25) n, m = map(int, sys.stdin.readline().split()) r = list(map(int, sys.stdin.read().split())) if len(r) != n: r = r[:n] # Initialize m+1 segments segments = [{'str_checks': [], 'int_checks': []} for _ in range(m + 1)] current_segment = 0 zero_count = 0 for num in r: if num == 0: zero_count +=1 if zero_count > m: continue # Ignore extra zeros beyond m current_segment +=1 if current_segment > m: current_segment = m # Clamp to m else: if num >0: segments[current_segment]['int_checks'].append(num) else: segments[current_segment]['str_checks'].append(-num) # Sort the checks in each segment for seg in segments: seg['str_checks'].sort() seg['int_checks'].sort() # Initialize DP INF = -1 << 60 dp_prev = [INF] * (m +1) dp_prev[0] =0 dp_final = [INF]*(m +1) for i in range(m +1): seg = segments[i] dp_next = [INF]*(m +1) for s in range(0, i +1): if dp_prev[s] == INF: continue t = i - s # Count passed Str checks num_Str_passed = bisect.bisect_right(seg['str_checks'], s) # Count passed Int checks num_Int_passed = bisect.bisect_right(seg['int_checks'], t) total_passed = dp_prev[s] + num_Str_passed + num_Int_passed if i <m: # Allocate to Str s_new = s +1 if s_new <=m: if total_passed > dp_next[s_new]: dp_next[s_new] = total_passed # Allocate to Int s_new = s if s_new <=m: if total_passed > dp_next[s_new]: dp_next[s_new] = total_passed else: # Last segment, assign to dp_final if total_passed > dp_final[s]: dp_final[s] = total_passed if i <m: dp_prev = dp_next else: break # Now, there might be a last segment after m allocations # To handle it, process the last segment if m allocations have been processed # But in the loop above, when i ==m, we have processed segments[m] and stored in dp_final # So proceed to get the maximum from dp_final max_passed = max(dp_final) print(max_passed if max_passed != INF else 0) if __name__ == "__main__": threading.Thread(target=main).start()Explanation of the Code:
-
Reading Input:
- Read
nandm. - Read the
nrecords and ensure that exactlymallocations (r_i = 0) exist.
- Read
-
Segmenting the Records:
- Iterate through each record and assign checks to the appropriate segment.
- Each segment corresponds to the sequence of checks between two allocations.
-
Sorting Checks:
- For each segment, sort the Strength and Intelligence checks to allow efficient counting of passed checks.
-
Dynamic Programming:
- Initialize a DP table where
dp_prev[s]holds the maximum number of checks passed withspoints allocated to Strength so far. - Iterate through each segment, updating the DP table based on whether you allocate the next point to Strength or Intelligence.
- For each allocation, count how many checks can be passed in the current segment and update the DP state accordingly.
- Initialize a DP table where
-
Final Calculation:
- After processing all segments, the answer is the maximum number of checks passed across all possible allocations.
Conclusion
This solution efficiently handles large input sizes by leveraging dynamic programming and pre-sorting of checks, ensuring that the solution runs within acceptable time limits even for the maximum constraints.
- You have