Problem Narrative

You’re on the ads optimization team at a global e-commerce marketplace serving 40M+ daily active users. During peak events (e.g., Black Friday), the platform must schedule a sequence of ad campaigns across the next n days. Each campaign has a “creative fatigue” cost per day, and the business requires that campaigns be split into exactly d contiguous flight windows (e.g., to align with budget approvals and compliance reviews). If you miss the SLA, the auction system falls back to a conservative strategy that can cost millions in lost revenue.

You need an algorithm that fits strict time limits: n can be up to 300 and d up to 10, so a naive DP that tries all splits will time out.

Formal Problem Statement

You are given an integer array cost of length n, where cost[i] is the fatigue cost of running campaigns on day i.

You must partition the array into exactly d non-empty contiguous segments. The cost of a segment is the maximum value in that segment (the worst fatigue day dominates the review risk). The total schedule cost is the sum of segment costs.

Return the minimum possible total cost. If it is impossible to partition into d non-empty segments (i.e., d > n), return -1.

Input / Output

• Input: cost: list[int], d: int
• Output: int (minimum total cost or -1)

Examples

Example 1

• Input: cost = [6, 5, 4, 3, 2, 1], d = 2
• Output: 7
• Explanation: Split as [6,5,4,3,2] and [1]. Segment maxima are 6 and 1, total 6 + 1 = 7. Any other split yields a larger sum.

Example 2

• Input: cost = [1, 1, 1], d = 4
• Output: -1
• Explanation: You can’t create 4 non-empty segments from 3 days.

Notes / Clarifications

1. Segments must be contiguous and cover all days.
2. Each segment must contain at least one day.
3. Aim for an approach faster than O(d * n^2); that typically times out at the upper bounds.

Constraints

• 1 <= n <= 300
• 1 <= d <= 10
• 0 <= cost[i] <= 10^6