Subtasks 2 and 4 are doable with simple pointers and dp. For subtask 3 we fix a range [l, r] and try to make it suitable (remove tasks when nessecary). Then use dp[n][k] = min batches in [1..n] having removed k tasks. For subtask 5 keep a similar idea, but instead of fixing [l, r] we fix l and then find the farthest suitable r, such that we will remove at most k tasks. For subtask 6 let's see if we can further optimize the transitions. It seems useful to store for every state (tasks processed, tasks removed) how many tasks were removed in the last batch. Note that we do NOT change the state to (tasks processed, tasks removed, tasks removed in the last batch). For every state there is a single relevant value of how many tasks are removed in the last batch. (Exercise for the reader) In the cases where we continue the last batch with the following task, we need to check two scenarios -- either this new task will be removed or it won't. (Lets include the notation left[n][k] for the leftmost end of the batch whose right end is n and excluded[n][k] for the number of removals in the last batch in the state (tasks processed = n, tasks removed = k)) If the task is removed, then dp[left[n][excluded[n - 1][k] + 1]][k - (excluded[n - 1][k] + 1)] + 1 = dp[n - 1][k] should be true. If the task isn't removed, then dp[left[n][excluded[n - 1][k]]][k - excluded[n - 1][k]] + 1 = dp[n - 1][k] should be true. If neither of these statements are true, the new task must be in a new batch: dp[n][k] = dp[n - 1][k] + 1