Most Runs With a Given Sum
Print the largest number of pairwise non-overlapping contiguous runs whose sums are all
exactly S. Values may be negative and S may be zero.
1 1 1 1 1, S = 2 -> 2 two disjoint pairs, with one element left over
1 2 3, S = 7 -> 0 no run sums to 7
## The greedy
Sweep left to right and close a run the moment one is available, then start completely
fresh. The detection is the standard prefix-sum trick: a run ending here sums to S
exactly when some earlier prefix equals prefix - S.
Written the obvious way, closing a run empties the set of seen prefixes and resets the
running prefix to 0. That is correct and it is how to think about it, but emptying a
hash set inside the loop is O(n) per reset, and with a reset at almost every index
the whole thing degrades to quadratic.
The fix keeps one set for the whole sweep and records, for each prefix VALUE, the latest INDEX at which it occurred. A run is then available when that stored index is at or after the last cut:
seen = { 0 -> 0 }, lastCut = 0, prefix = 0, count = 0
for i in 1..n:
prefix += a[i-1]
j = seen[prefix - S] if present
if j exists and j >= lastCut:
count++; lastCut = i
seen[prefix] = i always, overwriting
Storing only the LATEST index is enough: if the latest occurrence of prefix - S is
before the last cut then every occurrence is, and no run starting inside the free region
sums to S.
## Why closing early is right
Take an optimal family of runs and look at its leftmost run. The greedy's first run ends no later, because the greedy closes at the first opportunity. So replacing the optimal family's first run with the greedy's leaves at least as much array free to the right, and everything after it still fits. Repeat on the remainder, and the greedy's count is never smaller.
That is the same exchange argument as problems 457, 461 and 462, applied to a condition that is an equality rather than an ordering. Recognising it under the disguise is the skill this problem tests.
## Why the cut must be respected
Whichever form you write, nothing before the cut may be reused as a run's left boundary.
A solution that keeps the full prefix history with no lastCut test lets a later run
start before the cut, so two reported runs overlap and the count is too high.
3 1 2 3 1 2 with S = 3 answers 4, from [3], [1 2], [3], [1 2]. Every
index is used, so this is also the case that catches recording the prefix at a cut point:
the very next run must be allowed to start exactly there, which is why seen[prefix] = i
runs on every iteration including the ones that close a run.
## Zero and negatives
S = 0 is legal. 0 0 0 with S = 0 answers 3, and 1 -1 1 -1 1 with S = 0
answers 2. Both need the 0 -> 0 seed in seen, which is what lets a run
starting at the very beginning be recognised.
Negatives mean prefix sums are not monotonic, so a sliding window cannot be used and the hash set is not optional.
Sums reach 2 * 10^5 times 10^9, so prefixes need 64 bits.