Best k-day run in a cyclic sprint schedule

Flatten the schedule into a sequence of daily points: a sprint of length d
contributes 1, 2, ..., d. The schedule repeats, so the sequence is circular,
and we want the circular window of exactly k consecutive days with the
largest sum.

Brute force. Expand every sprint into its days (T = sum(days) values)
and slide a window of length k around the circle with a running sum. That
is O(T), but T can be huge when sprints are long (lengths up to 10^9 are a
common constraint for this kind of problem), so expanding days is not acceptable. We need something
that is linear in the number of sprints, n.

Key observation: an optimal window ends on the last day of some sprint.
Take any window whose last day is day j of a sprint of length d, with
j < d. Shifting the window one day to the right gains j + 1 and loses
the value x of its first day.

• While neither end crosses a sprint boundary, both the gained and the lost
  value grow by exactly 1 per shift, so the change per shift is constant. The
  total is linear in the shift, and the best position in that stretch is at
  one of its ends.
• One end of the stretch is "right edge reaches a sprint end" (what we want).
  The other is "left edge sits on day 1 of a sprint". From there, a right
  shift loses 1 and gains j + 1 >= 2, which strictly helps, so we keep
  moving right.

So we only need to test n candidate windows: one ending at the end of each
sprint.

Evaluating one candidate in O(log n). Unroll the circle once
(days + days) and build two prefix sums over it: days so far, and points
so far (a full sprint of length d is worth d(d+1)/2). For a window ending
at the end of sprint e (with e in the second copy, so the window never
runs off the left side when k <= T):

1. start = end - k is the day just before the window.
2. Binary-search the sprint s containing day start + 1.
3. Sprints s+1 .. e are fully inside: read their points from the prefix
   sum.
4. Sprint s contributes only its last r days, worth
   (d-r+1) + ... + d = r(2d - r + 1)/2. Taking the tail matters: the
   window starts mid-sprint, so it gets that sprint's high-value days.

If k exceeds T, every full loop is forced and contributes the same total,
so take k mod T for the window and add (k div T) times the points of one
loop.

Invariants: day_pre[i] is the number of days in the first i sprints of
the unrolled array; 1 <= r <= doubled[s]; the window covers days
(start, end] exactly.

from bisect import bisect_left
from itertools import accumulate


def tri(m: int) -> int:
    """Points for a full sprint of m days: 1 + 2 + ... + m."""
    return m * (m + 1) // 2


def tail_points(d: int, r: int) -> int:
    """Points for the last r days of a d-day sprint: (d-r+1) + ... + d."""
    return r * (2 * d - r + 1) // 2


def max_sprint_points(days: list[int], k: int) -> int:
    n = len(days)
    total_days = sum(days)
    if n == 0 or k <= 0 or total_days == 0:
        return 0
    cycles, k = divmod(k, total_days)          # whole loops are forced
    base = cycles * sum(tri(d) for d in days)
    if k == 0:
        return base

    doubled = days + days                       # unroll the cycle once
    day_pre = [0] + list(accumulate(doubled))   # day_pre[i] = days in doubled[:i]
    pts_pre = [0] + list(accumulate(tri(d) for d in doubled))

    best = 0
    # Window ends at the last day of doubled[e], for e in n .. 2n-1.
    for e in range(n, 2 * n):
        end = day_pre[e + 1]
        start = end - k                         # window covers days (start, end]
        # first sprint s whose end lies after `start`
        s = bisect_left(day_pre, start + 1) - 1
        full = pts_pre[e + 1] - pts_pre[s + 1]  # sprints s+1 .. e, whole
        r = day_pre[s + 1] - start              # days taken from sprint s (its tail)
        best = max(best, full + tail_points(doubled[s], r))
    return base + best


if __name__ == "__main__":
    assert max_sprint_points([3, 1, 4], 5) == 13   # 3 4 | 1 2 3 wraps around
    assert max_sprint_points([5], 3) == 12         # 3 + 4 + 5
    assert max_sprint_points([4, 1], 5) == 11
    assert max_sprint_points([1, 1, 1], 2) == 2
    assert max_sprint_points([3, 1, 4], 10) == 24  # one full loop (14) + best 2 days (10)
    print("ok")

• Time: O(n log n) for n sprints: O(n) to build the prefix sums over
  the unrolled array, then n candidates with one binary search each. A two
  pointer sweep (the start sprint only moves forward as e grows) makes it
  O(n).
• Space: O(n) for the unrolled array and the two prefix sums.
• Independent of the number of days, so sprint lengths up to 10^9 are fine.
  Python integers do not overflow; in Java or C++ use 64-bit sums.

• days = [3, 1, 4], k = 5 -> 13 (the circular run 3, 4 | 1, 2, 3: the
  last two days of sprint 2, then all of sprint 0 in the next loop).
• days = [5], k = 3 -> 12 (last three days 3 + 4 + 5).
• days = [4, 1], k = 5 -> 11 (4 + 1 + 1 + 2 + 3, wrapping).
• days = [1, 1, 1], k = 2 -> 2 (every day is worth 1).
• days = [2, 5], k = 3 -> 12 (3 + 4 + 5, entirely inside the long sprint).
• days = [4, 2, 3], k = 6 -> 15.
• days = [7], k = 7 -> 28 (the whole loop, k == T).
• days = [3, 1, 4], k = 10 -> 24 (k > T = 8: one full loop worth 14, plus
  the best 2-day window 3 + 4, worth 10).
• Edge: k = 1 returns max(days); k = 0 returns 0.
• Randomized check against the day-by-day brute force for small inputs.

1. Linear time. Replace the binary search with a pointer s that only
   advances as e advances (the window start is monotone). Same prefix sums,
   O(n) total.
2. Return the window, not just the sum. Track the best e and s; report
   the starting sprint and day (doubled[s] - r + 1, mod n) and the end
   sprint.
3. Different scoring per day. If day j of sprint i is worth an
   arbitrary f(i, j) that is still increasing within each sprint, the
   alignment argument still points to ends of sprints, but you need a
   per-sprint suffix-sum formula (or precomputed suffix sums when sprints are
   short). If points are not monotone within a sprint, the argument breaks and
   you fall back to a sliding window over expanded days.
4. Many queries for different k. Precompute the prefix sums once; each
   query is then O(n) (or O(n log n)). For many queries, note the answer
   per candidate e is a piecewise quadratic in k, which supports offline
   tricks, but stating the O(n) per query is usually enough.
5. Non-cyclic schedule. Drop the unrolling; only candidates with
   day_pre[e+1] >= k are valid, plus the window that starts at day 1 of the
   first sprint if k does not fit after a sprint end.

Mid-level (L4)

• Models days as a circular array and gets a correct sliding-window solution
  over expanded days.
• Recognizes that expanding days is too slow when sprint lengths are large.
• Handles the wrap-around correctly (array doubling or modulo indexing).

Senior (L5)

• States and justifies that an optimal window ends on a sprint's last day.
• Builds prefix sums over sprints and uses the tail-sum formula for the
  partial first sprint, getting O(n log n) or O(n).
• Tests the edge cases: k = 1, k = T, one sprint, and windows that wrap.

Staff (L6+)

• Gives a crisp exchange argument (the sum is linear between boundaries, so
  the maximum is at a boundary) and knows when it fails (non-monotone points).
• Generalizes cleanly to k > T, many queries, or other scoring functions.
• Calls out overflow in fixed-width languages and writes the code so the
  arithmetic is visibly correct.