Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

The only difference between easy and hard versions is the constraints. Vova likes…

  1. User

    The only difference between easy and hard versions is the constraints.

    Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of n consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the i-th picture has beauty a_i.

    Vova wants to repost exactly x pictures in such a way that:

    • each segment of the news feed of at least k consecutive pictures has at least one picture reposted by Vova;
    • the sum of beauty values of reposted pictures is maximum possible.

    For example, if k=1 then Vova has to repost all the pictures in the news feed. If k=2 then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

    Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions. Input

    The first line of the input contains three integers n, k and x (1 ≤ k, x ≤ n ≤ 200) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

    The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the beauty of the i-th picture.

    Output

    Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

    Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.

    Examples

    Input

    5 2 3 5 1 3 10 1

    Output

    18

    Input

    6 1 5 10 30 30 70 10 10

    Output

    -1

    Input

    4 3 1 1 100 1 1

    Output

    100

  2. DeepSeek Assistant

    We need to solve the problem. This is a DP problem similar to "segment covering" constraints. We have n positions, need to select exactly x positions such that every segment of length k contains at least one selected position. Equivalent to saying that the distance between consecutive selected positions cannot exceed k. Actually, if we have selected positions at indices p1 < p2 < ... < px, we need that for any i, pi+1 - pi <= k? Let's examine: The condition is: each segment of at least k consecutive pictures has at least one repost. That is, for any contiguous segment of length k (i.e., positions i to i+k-1), at least one selected. This is equivalent to "the maximum gap between consecutive selected positions (or before the first and after the last) is at most k". More precisely, we need that between any two selected positions the distance <= k, and also the first selected must be within k of the start (i.e., position 1 is the first picture; segment [1, k] must have a selected, so p1 <= k), and similarly the last selected must be >= n - k + 1 (since segment [n-k+1, n] must have a selected). This is known as a "k-cover" constraint: selecting positions to dominate intervals of length k.

    Thus we need to pick exactly x positions with these constraints to maximize sum of a_i.

    n up to 200, so DP O(n^2 x) maybe okay. The hard version? This is the easy version with constraints n <= 200. Hard version probably n up to 5000 or 1e5. But we only need solve easy version.

    We can define DP[i][j] = max sum for selecting j pictures from first i pictures, with the condition that the chosen pictures satisfy the coverage constraints up to i. But need to ensure that after i, the constraints for segments entirely before i are satisfied, but also need to consider future constraints? Usually we can process sequentially and ensure that the gap condition holds. Since coverage constraint is about all segments of length k, it's equivalent to "the distance between consecutive selected positions is <= k", with the first selected at <= k and last selected at >= n - k + 1. This can be enforced by DP if we also consider the position of the last selected and the distance from the end.

    Alternative: Use DP[i][j] where i is index and j is count, and we store maximum sum such that we have selected j pictures among first i, and we also ensure that all segments of length k that end at i (or up to i) are covered? The condition for all segments ending at i: For any segment that ends at i and length k (i.e., [i-k+1, i]), if i >= k, it must contain a selected. So when we process i, we need to know if in the last k positions up to i, we have selected at least one. This is reminiscent of covering intervals with points.

    We could enforce that the gap between selected positions is <= k. That's a simpler constraint.

    Let's formalize:

    We need to choose a set S of indices such that |S| = x, and for all i from 1 to n-k+1, S ∩ [i, i+k-1] is non-empty.

    Equivalent: For any interval of length k, there is a selected point. This is like "hitting set" for intervals of length k. For points on a line, this condition is exactly that the distance between consecutive selected points is at most k, and also first selected must be <= k, last selected must be >= n-k+1.

    Proof: Suppose we have selected points p1 < p2 < ... < px. For any i, if the gap between p_j and p_{j+1} > k, then the interval (p_j, p_{j+1}) of length > k might have no selected; but specifically the interval starting at p_j+1 up to p_{j+1}-1? Actually, consider the interval that starts at p_j+1 and ends at p_j + k? But need to find an interval of length k with no selected. If p_{j+1} - p_j > k, then take interval from p_j+1 to p_j+k (length k). Since p_j+1 > p_j+k? Wait, if p_{j+1} - p_j > k, then p_j+1 >= p_j + k + 1. Then interval [p_j+1 - k, p_j]? Let's find: The interval [p_j+1 - k, p_j] would be of length k? Actually p_j+1 - k <= p_j if p_{j+1} - p_j > k? p_{j+1} - k > p_j. So p_j+1 - k > p_j. That interval [p_j+1 - k, p_{j+1} -1] is of length k-1? Let's do standard: For a set of points to hit all intervals of length k, the maximum gap between consecutive selected points must be at most k-1? Need to be careful.

    Consider points on a line. Intervals of length k. Suppose we have selected points at positions 1 and 5, and k=3. Check intervals: [1,3] has point 1, ok. [2,4] has? 2-4 contains no selected? 5 is >4, 1 is <2. So [2,4] length 3: positions 2,3,4, none selected. So fails. Gap = 4 (5-1=4) which is >3? Actually gap between selected points is 4. But is condition gap <= k? Here gap = 4 > 3, fails. What about gap <= k? k=3, so gap must be <=3? But if gap =3, say positions 1 and 4, gap=3. Check intervals: [1,3] ok; [2,4] includes 4? Yes, 4 is selected, so ok. [3,5] includes 4? 3,4,5 includes 4 selected; also [4,6] etc. So gap=3 works. So maximum gap between consecutive selected positions must be <= k. That's consistent.

    Now the boundaries: The first selected point must be at position <= k, because interval [1,k] must be covered. So p1 <= k. Similarly the last selected point must be at position >= n - k + 1, because interval [n-k+1,n] must be covered. So px >= n - k + 1.

    Thus constraint: Choose exactly x indices p1<...<px such that p1 <= k, px >= n - k + 1, and for all j, p_{j+1} - p_j <= k.

    Also note that x must be at least ceil(n/k)? Actually the minimal number of points needed to cover intervals of length k is ceil(n/k)?? Consider n=5,k=2: minimal points needed? Need to cover intervals of length 2: positions like [1,2], [2,3], [3,4], [4,5]. This is like each point covers up to k positions? The minimal number is ceil(n/k)?? For n=5,k=2: ceil(5/2)=3. Check: select positions 2,4: intervals: [1,2] has 2; [2,3] has 2; [3,4] has 4; [4,5] has 4. So 2 points work, not 3. So ceil(n/k) is not correct. Actually it's like you need to cover the line with intervals of length k such that each point can cover an interval of length k? The condition is that every length-k segment must contain a point. The minimal number is ceil(n/k)? Wait, think: For a line of length n, if you place points spaced exactly k apart, you guarantee that any interval of length k contains at least one point? For example, n=5,k=2: if you place points at 2 and 4 (spaced 2 apart), any interval of length 2 will contain at least one? Check interval [1,2]: contains 2; [2,3]: contains 2; [3,4]: contains 4; [4,5]: contains 4. Yes. So spacing of k works. In general, if you place points at positions k, 2k, ..., that's about n/k points. But if n is not multiple of k, the last point might be placed at something like n - k + 1? Actually to cover last segment [n-k+1,n], the last point must be >= n-k+1. If you place points at multiples of k, say k,2k,..., floor(n/k)*k. But if floor(n/k)*k < n-k+1? For n=5,k=2, floor(5/2)*2=4, which is >= 3 (n-k+1=4)? Actually n-k+1=4, so 4 works. For n=6,k=2: n-k+1=5; floor(6/2)*2=6, which works but may be > n? Actually 6 <= n so okay. So the number of points needed is at most ceil(n/k). But the minimal number is the minimum number of points needed to cover all intervals of length k. That is exactly the size of a minimum hitting set for intervals of length k on a line of discrete points. For unit length intervals on integer points? Actually points are integer positions 1..n. Intervals are contiguous sets of k positions. The minimal number is ceil(n/k)?? Let's test n=6,k=2: ceil(6/2)=3. Can we do with 2 points? Try positions 2 and 5? Check intervals: [1,2] ok, [2,3] ok, [3,4]? Contains 2? 2 is not in [3,4]; 5 not in [3,4]. So fails. Positions 2 and 4? [1,2] ok, [2,3] ok, [3,4] contains 4 ok, [4,5] contains 4 ok, [5,6]? Contains 4? no, 5? no, fails. So need 3 points: e.g., 2,4,6? Actually 6 not needed because last segment [5,6] need a point, could use 5. So maybe minimal is 3. Indeed ceil(6/2)=3. For n=5,k=2, ceil(5/2)=3, but we found 2 works. So ceil(n/k) is not always minimal. Let's compute minimal needed: We want to cover all positions? Actually it's a covering problem: intervals of length k, each point can cover intervals that contain it. Equivalent to: we need to choose points such that there is no gap of length k without a point. The condition is that the maximum gap between consecutive selected points (including boundaries) is <= k. Including boundaries: treat virtual point at position 0 (before first) and n+1 (after last). Then we need p1 - 0 <= k? Actually the first point must be within k of the start: p1 <= k. That can be seen as gap from 0 to p1 <= k? If we set imaginary point at 0, then p1 - 0 <= k? But 0 is not a picture; better to treat start condition as: the first selected index must be <= k. That ensures that the segment from 1 to k is covered. Similarly, imaginary point at n+1: (n+1) - px <= k? That would be n+1 - px <= k => px >= n+1 - k = n - k + 1. Yes. So including boundaries we need max gap between successive selected points (including start and end) <= k. So the minimal number of points needed is minimal integer m such that you can place m points with max gap <= k, covering [1,n]. This is like covering a segment of length n (with discrete points) with intervals of length k? Actually if we treat each point as covering a radius? But easier: The condition that max gap <= k implies that the number of points needed m satisfies: (m+1) * k >= n? Let's derive: With m points placed at positions p1,...,pm, and boundaries 0 and n+1. The gaps: gap0 = p1 - 0, gap_i = p_{i+1} - p_i for i=1..m-1, gap_m = (n+1) - p_m. All gaps must be <= k. Sum of gaps = (n+1). So (m+1)*k >= n+1? Actually if each gap <= k, then (m+1)*k >= sum gaps = n+1. So m+1 >= ceil((n+1)/k) => m >= ceil((n+1)/k) - 1. Compute for n=5,k=2: (n+1)=6, ceil(6/2)=3, minus 1 = 2. So minimal m=2, works. For n=6,k=2: (n+1)=7, ceil(7/2)=4, minus 1 = 3. So minimal m=3, works. So the formula m_min = ceil((n+1)/k) - 1? Let's check n=4,k=3: (n+1)=5, ceil(5/3)=2, minus 1 =1. So minimal points needed =1. Indeed one point at position? Must satisfy p1 <=3 and p1 >= n-k+1 =2. So any position 2 or 3 works. So one point is enough. Good. So we can compute minimal x_min = ceil((n+1)/k) - 1. But careful: For n=1,k=1: (2)/1=2, ceil2=2, minus1=1 => x_min=1, which is correct (must select the only picture). For n=1,k=2? But k ≤ n? Actually constraints 1 ≤ k ≤ n, so k <= n. So ok.

    Thus we need exactly x, and we need to check if x is at least x_min and at most something? Upper bound: can we always select x pictures? If we need exactly x, we can always add extra points as long as they don't violate the gap condition? But adding extra points might violate? Actually extra points can be inserted anywhere; they will not increase gaps, they decrease gaps, so they will maintain the condition. So any x >= x_min is possible. However there might also be an upper bound? Since we have n pictures, we can select at most n. But also the condition "exactly x pictures" is given. So if x < x_min it's impossible -> print -1. Also if x > n, impossible but given x ≤ n.

    Thus first check feasibility: if x < ceil((n+1)/k) - 1, then -1. Actually need to confirm formula: To cover all intervals of length k, we need the gap condition. The minimal number of points is the minimum m such that (m+1)*k >= n+1? But more precisely, we need to place points such that the maximum gap between consecutive points (including boundaries) is ≤ k. The minimal m is the smallest m such that we can have m points with that property. This is essentially covering a line segment of length n with intervals of length k? But think: if we have m points, the maximum possible total length covered with given max gap is (m+1)*k (since each of the m+1 gaps can be up to k). So we need (m+1)*k ≥ n+1 (since total length from 0 to n+1 is n+1). So m_min = ceil((n+1)/k) - 1. So check if x >= m_min.

    Now we need to maximize sum. DP can be done as: dp[i][j] = maximum sum using j pictures among first i pictures, and the coverage condition holds for all segments completely within first i (i.e., for any segment of length k that lies entirely within [1,i], there is at least one selected). But we also need to ensure the future condition about the last selected? When we finish at i=n, we need the coverage for all segments, so we must also enforce that the last selected is at least n-k+1. However if we just enforce the gap condition, we can incorporate the start and end constraints. The gap condition includes boundaries: we need p1 <= k and px >= n-k+1. This is equivalent to ensuring that the gap from the start (0) to first selected is ≤ k, and gap from last selected to n+1 is ≤ k. In DP, we can treat imaginary start at 0 and end at n+1. For DP forward, we can ensure that the first selected is ≤ k. That can be handled by only allowing initial selections up to k? Actually we need to guarantee at the end that the last selected is within k of n+1. So we need to keep track of the last selected position to verify that the final gap to n+1 is ≤ k. So DP state could include the position of the last selected to enforce future constraint. But since n ≤ 200, we can use DP[i][j] where i is the index up to which we have considered, and we also store the last selected index (or maybe the distance from the last selected). However we also need to ensure that gaps are ≤ k. So if we decide to select positions, the distance between consecutive selections must be ≤ k. So DP can be: dp[i][j] = max sum with j selections, and the last selected is exactly i (i is selected). Then we can transition from previous selection p where i-p ≤ k, and p ≤ i-1. Then dp[i][j] = a_i + max_{p in [i-k, i-1] ∩ selected} dp[p][j-1]. However we also must ensure that before the first selection, the start condition (gap from 0) is ≤ k, which is equivalent to first selection index ≤ k. So for first selection, we can initialize dp[i][1] = a_i if i ≤ k (since then gap from 0 to i ≤ k). If i > k, then dp[i][1] is invalid (-inf). But also we might have not selected any pictures yet? We need exactly x selections. So we handle first selection separately.

    At the end, we need that the last selection index i satisfies n+1 - i ≤ k, i.e., i ≥ n - k + 1. So answer = max_{i ≥ n-k+1} dp[i][x].

    But does this DP also ensure that all intermediate segments are covered? The gap condition between selections ensures that any segment that lies entirely between two selected points is of length ≤ k? Actually if consecutive selected positions p and q have q-p ≤ k, then any interval of length k that lies entirely between p and q? But consider an interval that starts before p and ends after p? The condition that each interval of length k must contain at least one selected point is equivalent to the gap condition. So if we enforce that all gaps between consecutive selected points (including start and end) are ≤ k, then the coverage holds. The DP that ensures each step only allows transitions from p with i-p ≤ k, and initial condition p1 ≤ k, final condition i ≥ n-k+1, then all gaps are ≤ k. Additionally, we need to ensure that we don't have any "internal" gaps that are not between consecutive selected? That's automatically taken care by the chain of selections. However, there is a subtlety: If we have selections at p and q, and the gap is ≤ k, then any interval of length k within (p,q]? For example, consider p=1, q=4, k=3: gap=3 ≤ k. Interval [2,4] length 3 includes q=4, okay. Interval [1,3] includes p=1. Actually it's fine. Generally, for any interval of length k, if its left endpoint is in [p+1, p+?], we need to ensure it contains either p or q. With gap ≤ k, any interval of length k will intersect at least one of the points. Formal: The maximum uncovered segment between p and q is the gap minus 1 (if we consider discrete points). If gap ≤ k, then any interval of length k will cover at least one endpoint. So okay.

    Thus DP approach is valid.

    Complexity: O(n^2 * x) if we do for each i, j, and look at all p from i-k to i-1. Since k ≤ n ≤ 200, worst-case O(n^2 * x) = 200200200 = 8e6, fine. But we can also optimize with prefix max but not needed.

    We need to be careful about the base case: dp[i][1] = a_i if i <= k else -inf.

    Then for j from 2 to x, for i from 1 to n, compute dp[i][j] = a_i + max_{p in [max(1, i-k), i-1]} dp[p][j-1], provided that dp[p][j-1] is valid. Note that we don't require p ≤ k? That's already covered by the condition that the first selection is ≤ k, which is enforced in dp[p][1] initialization. For j>1, p might be any index that has dp[p][j-1] valid, and p must be such that the distance to i is ≤ k. That ensures gap condition.

    But also what about the requirement that between the start and first selection, the gap is ≤ k? That is enforced by only allowing dp[i][1] for i ≤ k. Similarly, we also need that between the last selection and the end, the gap is ≤ k. So answer only counts dp[i][x] where i ≥ n - k + 1.

    But what about the possibility of not selecting a picture at the very end? The last selected index i could be less than n - k + 1, then the segment [n-k+1, n] would have no selection, violating condition. So indeed we require i ≥ n - k + 1.

    Also, what about the case where x = 0? But x≥1 as per constraints? Actually x ≥ 1? Input says 1 ≤ k, x ≤ n, so x ≥ 1. So we don't worry about zero.

    Now check example: n=5,k=2,x=3, a=[5,1,3,10,1].

    Compute dp. For j=1, allowed i<=2. dp[1][1]=5, dp[2][1]=1. j=2: For i from 1 to 5. i=1: need p in [max(1,1-2= -1?), i.e., from 1 to 0 none, so dp[1][2] invalid. i=2: p in [max(1,0)=1 to 1], check dp[1][1]=5 -> dp[2][2]=1+5=6. i=3: p in [max(1,1)=1 to 2], dp[1][1]=5, dp[2][1]=1 -> max=5 => dp[3][2]=3+5=8. i=4: p in [max(1,2)=2 to 3], dp[2][1]=1, dp[3][1]? dp[3][1] invalid because i=3>2? Actually dp[3][1] not allowed (since i>k). So only dp[2][1]=1 => dp[4][2]=10+1=11. i=5: p in [max(1,3)=3 to 4], dp[3][1] invalid, dp[4][1] invalid? Actually dp[4][1] invalid because 4>2. So none? So dp[5][2] invalid. j=3: i from 1 to 5. i=1: need p from [max(1,-1)=1 to 0] none -> invalid. i=2: p in [1 to 1], dp[1][2] invalid -> invalid. i=3: p in [1 to 2], check dp[1][2] invalid, dp[2][2]=6 => dp[3][3]=3+6=9. i=4: p in [2 to 3], dp[2][2]=6, dp[3][2]=8 => max=8 => dp[4][3]=10+8=18. i=5: p in [3 to 4], dp[3][2]=8, dp[4][2]=11 => max=11 => dp[5][3]=1+11=12.

    Now answer: we need i>= n-k+1 = 5-2+1=4. So consider dp[4][3]=18, dp[5][3]=12. Max is 18. So answer 18 matches.

    Second example: n=6,k=1,x=5, a=[10,30,30,70,10,10]. Check minimal x: ceil((n+1)/k)-1 = ceil(7/1)-1=7-1=6. So x_min=6, but x=5 <6, so impossible => -1. Indeed output -1. Good.

    Third example: n=4,k=3,x=1, a=[1,100,1,1]. Minimal x: ceil(5/3)-1 = ceil(1.6667)=2? Actually (n+1)=5, ceil(5/3)=2, -1 =1. So x_min=1, feasible. DP: j=1: allowed i<=k=3 => dp[1][1]=1, dp[2][1]=100, dp[3][1]=1. j=1 only. Answer: i >= n-k+1 = 4-3+1=2. So dp[2][1]=100, dp[3][1]=1? But dp[3][1] is valid? Actually i=3 >=2, so both considered, but dp[3][1]=1 is less, so answer 100. Output 100 matches.

    Thus DP works.

    But we must be careful about large a_i up to 1e9, sum up to 1e9 * 200 = 2e11, fits in 64-bit.

    Now implement.

    Check corner cases: x=0? Not allowed, but for completeness we could handle but not needed.

    Complexity: O(n^2 * x). n=200, x up to 200, so 8e6 operations, fine.

    We need to handle -infinity. Use -1e18 or something.

    We can also add feasibility check using min required x: if x < ceil((n+1)/k)-1, print -1. But note that the DP will also result in no valid dp[i][x] with i >= n-k+1 if impossible. However it's safer to check because DP may produce some value if it is possible but maybe DP will just be -inf. But we can rely on DP. But checking minimal x gives early -1. However there may be cases where x is >= min but DP might still find impossible because of some other reason? Possibly if some positions are forced? But given we can always add extra points, any x >= min is feasible. But is it always possible to select exactly x points? With x >= min, we can start with a minimal covering set, then insert extra points anywhere (e.g., just before the first or after the last, as long as they don't violate gap conditions? Actually adding extra points anywhere will only reduce gaps, so condition remains satisfied. So we can always increase count up to n. So feasible. So the feasibility condition is simply x >= min. But also we need to ensure x <= n. Since x ≤ n, okay. So we could simply compute dp and if answer remains -inf, print -1. But the minimal condition will be captured. However there might be subtlety: The DP only allows gaps <= k; inserting extra points may violate? No, it only makes gaps smaller. So if we have a valid set of size min, we can add any additional points (any positions) and still have gaps <= k? Wait, if we add a point in between two existing points, the gap reduces. So condition still holds. If we add a point before the first, it might increase the gap from the start? Actually we consider the gap from start to first selected point. If we add a point before the first, then the new first point becomes that earlier point. The gap from start (0) to the new first point is the index of the new first point. We must ensure that gap <= k. If we add a point at position 1, then gap=1 <= k, fine. But if we add a point at a position > k, that would violate the start condition because the new first point would be >k, and gap from start would be > k. However we could add points after the first but before the second, etc. So we can always add extra points without violating constraints as long as we add them in positions that keep the gaps ≤ k and maintain start/end constraints. But can we always increase from min to any larger x up to n? Possibly not if adding points forces the first point to be >k? Because if we add a point before the first point, the first point changes. So if the original first point is at position <=k, adding a point at a position >k would become the new first point? Actually if we add a point at position >k and that point is before the original first point? But the original first point is the smallest index. To add a new point with index less than current first point, we must place it at some index < p1. But p1 is <= k. If we place a new point at index i < p1, then the new first point will be i. For the start condition, we need i <= k. Since i < p1 <= k, i <= k automatically. So it's fine. So any i from 1 to p1-1 is <= k (since p1-1 <= k-1). So any insertion before first point is also within 1..k. So okay.

    Similarly, adding after last point, need i >= n-k+1? If we add a point after the last point, the new last point becomes that larger index, so need that index >= n-k+1. If we add at index i > p_last, then i must be >= n-k+1. But if p_last already >= n-k+1, then any i > p_last is <= n? But i could be less than n-k+1? Actually if p_last >= n-k+1, then any i > p_last is >= p_last+1, which might be < n-k+1 if p_last < n-k+1? But p_last >= n-k+1 by condition, so p_last+1 >= n-k+2 > n-k+1. So any i > p_last is automatically >= n-k+2 > n-k+1, so condition holds. So we can add points after the last without violating end condition.

    Thus any additional point added anywhere between existing points, or before first (within 1..k) or after last (within n-k+1..n) will maintain conditions. Actually before first we must be <= k, which is fine. So we can always increase the count by adding points at any allowed position that does not break constraints. But is it always possible to add a point at any position? For a given set of points, we can insert a new point at any index that is not already selected? But we must ensure that after insertion, all gaps <= k. Adding a point can only decrease gaps, so gaps become smaller or stay same. So it's always safe. The only potential issue: start and end constraints: if we add a point at index i that is less than the current first point, we need i <= k; that is automatically true if i is at least 1? Actually if i > k, then i > k and becomes new first point, but then the gap from start (0) to i would be i > k, violating condition. So we cannot add a point with index > k before the first point. But we can choose to add points only in positions <= k, which are always available as long as not all are selected? There are only k positions in [1,k], and we can at most select all of them. But if we already have min points, maybe we could fill up to n. Since n can be up to 200, we should be able to increase count to any number up to n as long as there are enough available positions? But what if we need to reach exactly x, but the number of available positions is n. Since we can select any subset of positions, as long as the constraints are satisfied, we can increase up to n. But is it always possible to select all n positions? Check condition: If we select all positions, then obviously every segment of length k has a selected picture because all are selected. So yes, all positions is valid. So from a minimal valid set, we can add any other positions; the constraints are monotonic: more selections doesn't break the condition. So indeed any x >= min is feasible. So we can rely on DP to find max sum, and if answer is -inf then it means no valid selection of exactly x points, but that would contradict feasibility? Unless DP has a bug. So it's fine.

    Thus algorithm:

    • Read n,k,x, a[1..n] (1-indexed).
    • Compute min_required = ceil((n+1)/k) - 1. If x < min_required or x > n (but x <= n), then print -1 and exit.
    • Initialize dp array of size (n+1) x (x+1) with -inf.
    • For i from 1 to n: if i <= k: dp[i][1] = a[i].
    • For j from 2 to x: for i from 1 to n: // compute dp[i][j] = a[i] + max_{p = max(1,i-k) to i-1} dp[p][j-1] best = -inf for p from max(1,i-k) to i-1: if dp[p][j-1] != -inf: best = max(best, dp[p][j-1]) if best != -inf: dp[i][j] = a[i] + best
    • After loops, answer = max_{i from n-k+1 to n} dp[i][x] (if n-k+1 <= 0? n-k+1 could be 1 if k>=n? But k <= n, so n-k+1 >= 1? For n=4,k=4 => n-k+1=1. So lower bound is at least 1.)
    • If answer is -inf, print -1 else print answer.

    But careful: If k > n? Actually constraints say k ≤ n, so n-k+1 >= 1? For n=3,k=3 => 3-3+1=1, ok. For n=2,k=2 => 1, ok. So fine.

    Now test with example:

    Example 1: works.

    Edge cases: n=1, k=1, x=1, a=[5]. min_required = ceil(2/1)-1=2-1=1 => x=1 ok. dp[1][1] = 5 because 1 <= 1? yes. answer: i from n-k+1 = 1-1+1=1 to 1 => dp[1][1] =5 => output 5. That's correct.

    n=1, k=1, x=0? Not allowed.

    n=2, k=2, x=1, a=[10,20]. Condition: each segment of at least 2 pictures? Since only one segment of length 2: [1,2] must have a repost, so we need at least 1 repost. x=1 is exactly 1. Also need the selected picture to be within k of both ends? Actually condition: segments of length k (=2). So we need [1,2] covered, so we must select either 1 or 2. Both are allowed. But also the condition about gaps: first selected <= k=2, last selected >= n-k+1=1. So both allowed. Max sum = max(10,20)=20. DP: j=1: allowed i <= k=2 => dp[1][1]=10, dp[2][1]=20. Answer: i >= n-k+1=1 => both, max=20. Works.

    n=2, k=2, x=2, a=[10,20]. Need select both? x=2, but condition: each segment length 2 must have at least one; selecting both is fine. But does it satisfy gap? p1=1<=2, p2=2, gap=1<=2, last >=1. So valid. Sum=30. DP: j=1 as before; j=2: for i=1: p from max(1,1-2)=1 to 0 none -> invalid. i=2: p from max(1,0)=1 to 1, dp[1][1]=10 => dp[2][2]=20+10=30. Answer: i>=1 => i=2 gives 30. So 30. Works.

    Now test n=3, k=2, x=2. min_required = ceil(4/2)-1=2-1=1, so possible. a=[5,5,5]. DP: j=1: i<=2: dp[1][1]=5, dp[2][1]=5. j=2: i=1: none; i=2: p=1 gives 5 => dp[2][2]=5+5=10; i=3: p from max(1,1)=1 to 2: dp[1][1]=5, dp[2][1]=5 => max 5 => dp[3][2]=5+5=10. Answer: i >= n-k+1 = 3-2+1=2 to 3: dp[2][2]=10, dp[3][2]=10 => max=10. But we could also select positions 1 and 3? Check if that's allowed: p1=1 (<=2), p2=3 (gap=2 <=2), last=3 >=2 (since n-k+1=2). So allowed sum=10. So DP gives 10, okay.

    Now test a case where k=3, n=5, x=2. min_required = ceil(6/3)-1=2-1=1, possible. Suppose a = [1,2,3,4,5]. We need to select 2 positions with gaps <=3, first <=3, last >=3 (n-k+1=3). So possible selections: (1,2), (1,3), (1,4)?? Check (1,4): gap=3 <=3, last=4>=3 -> ok. (1,5): gap=4 >3 not ok. (2,3): gap=1, last=3>=3 -> ok. (2,4): gap=2, last=4>=3 ok. (2,5): gap=3? 5-2=3 <=3, last=5>=3 ok. (3,4): first=3<=3? 3<=3 ok, gap=1, last=4>=3 ok. (3,5): gap=2, ok. (4,5): first=4>3? 4>3 violates start condition because [1,3] must have a repost. So invalid. Also (2,3) etc. So DP should compute max sum. Let's manually: max sum among these: (4,5) invalid, (3,5)=8, (2,5)=7, (1,5)=6 but invalid because gap=4>3, actually (1,5) gap 4 invalid. (1,4)=5, (2,4)=6, (3,4)=7, (1,3)=4, (2,3)=5, (1,2)=3. So best is (3,4)=7 or (3,5)=8? (3,5) sum=8, valid? first=3 (<=3), gap=2, last=5>=3, yes. So max sum=8. DP: j=1: i<=3: dp[1][1]=1, dp[2][1]=2, dp[3][1]=3. j=2: for i=1: none; i=2: p from max(1,-1)=1 to1: dp[1][1]=1 => dp[2][2]=2+1=3; i=3: p from 1 to2: max(dp[1][1]=1, dp[2][1]=2)=2 => dp[3][2]=3+2=5; i=4: p from max(1,1)=1 to3: max(1,2,3)=3 => dp[4][2]=4+3=7; i=5: p from max(1,2)=2 to4: dp[2][1]=2, dp[3][1]=3, dp[4][1]? dp[4][1] invalid because i=4>3? so max=3 => dp[5][2]=5+3=8. Answer: i>= n-k+1 = 5-3+1=3 => consider i=3..5: dp[3][2]=5, dp[4][2]=7, dp[5][2]=8 => max=8. Good.

    Thus DP works.

    Now we must be careful about the possibility of selecting exactly x pictures but with gaps > k? DP ensures gaps ≤ k.

    Now check minimal required condition: Should we enforce that x must be >= min? If we don't enforce, DP might return -inf if impossible. But it's safe. However DP may be O(n^2*x) and always compute values. We'll compute and then if answer is -inf, output -1.

    Now implement.

    Potential pitfalls: Use 64-bit integers. Use large negative for -inf, e.g., -1e18 or LLONG_MIN/2. Since a_i up to 1e9 and n up to 200, max sum <= 2e11, so -1e18 safe.

    Implementation details:

    We'll do 1-indexed array a[1..n].

    Initialize dp as vector of vectors (n+1, vector(x+1, -INF)). We'll set -INF = -1e18.

    Loop i=1..n: if i <= k: dp[i][1] = a[i].

    For j=2..x: for i=1..n: best = -INF for p = max(1, i-k) to i-1: if dp[p][j-1] > best: best = dp[p][j-1] if best != -INF: dp[i][j] = best + a[i]

    After DP, answer = -INF for i = max(1, n-k+1) to n: answer = max(answer, dp[i][x]) if answer == -INF: print -1 else print answer.

    But need to confirm that dp[i][x] for i < n-k+1 could also be valid if we have more pictures after i? Wait, the DP only considers selections up to i, and i is the last selected index. If i < n-k+1, then the last selected is before the required area, meaning the segment [n-k+1, n] would not have a selected picture, violating condition. So indeed we must restrict to i >= n-k+1.

    But what about the possibility that the last selected is not i but we have more selections after i? No, dp[i][x] means exactly x selections and the last selected is i. So it's fine.

    Now consider if x=1: Then dp[i][1] = a_i if i <= k; but also we need i >= n-k+1. So for x=1, the picture must be both within first k and within last k region. So the index must be in intersection of [1,k] and [n-k+1,n]. That intersection is nonempty if and only if n-k+1 <= k, i.e., n <= 2k - 1? Actually for n=4,k=3, intersection is [1,3] ∩ [2,4] = [2,3] nonempty. In general, the condition for existence of a single point covering both ends is that the segment length is at most 2k-1? Let's derive: n - k + 1 <= k => n <= 2k - 1. If n > 2k-1, then a single point cannot satisfy both start and end constraints because the first k and last k intervals do not overlap. Then we need at least 2 points. The DP will reflect that: For x=1, dp[i][1] for i <= k, but answer only from i >= n-k+1. So if n > 2k-1, then there is no i satisfying both, so answer = -inf => -1. That matches the min required: For n=5,k=2, min required = ceil(6/2)-1 = 3-1=2, so x=1 <2 impossible. So DP correctly yields -1.

    Now verify with example: n=5,k=2,x=1 => DP only dp[1][1]=5, dp[2][1]=1; answer from i>=4, none, so -1. Good.

    Thus DP works.

    Now check if any other conditions: maybe the DP could produce a valid set where first selected is not within k because we allow transitions from p that might have dp[p][j-1] with p > k? But dp[p][j-1] is only defined if it satisfied the constraints up to p. For j-1 >=2, the first selected in that dp[p][j-1] will be <= k because of initialization. So it's fine.

    Now consider x = n? That means selecting all pictures. This always satisfies the condition because every segment has a selected picture (since all are selected). Is there any restriction on gaps? All gaps are 1 <= k, so fine. Also first and last conditions hold. So dp should compute sum of all a_i. Let's see if our DP can produce that: For j=n, we need to pick all positions. This would correspond to dp[i][j] where the previous selection is i-1 (since gap must be <=k, and 1 <= k always). So dp[i][j] = a_i + dp[i-1][j-1]. Since j increases, we will need to have dp[i-1][j-1] computed. Base case j=1 with i <= k. But for i > k, dp[i][1] is -inf, so we cannot start with a first selection > k. But for j=n, the first selected must be <= k, so the first selected index is some i1 <= k. Then subsequent selected indices must be each within k of previous. Since we need to select all n positions, the only way is to select consecutive indices starting from some i1 <= k and then each subsequent index differs by 1. But if we select all positions, the first selection is 1 (since we must select all, we must select 1 as well). However, if we select all positions, the first selected index is 1 (or any index if we skip some? But selecting all positions means we select 1). So first index is 1, which is <= k. So dp[1][1]=a_1. Then dp[2][2]=a_2 + dp[1][1], etc. But what about j=n for n > k? For dp[some index i][j] we require that we came from a previous index within k. Since we want to select all positions, we can do: dp[1][1] -> dp[2][2] -> dp[3][3] -> ... -> dp[n][n]. That works because each transition from i-1 to i with difference 1 <= k. So dp[n][n] should be sum a_i. Let's check if our DP loops allow j up to n, and for each i, we iterate p from i-k to i-1. For i=2, p includes 1, dp[1][1] valid. For i=3, p includes 2, dp[2][2] valid? But dp[2][2] needs to be computed before dp[3][3]? Since we loop j from 2 to x, and for each j we compute dp[i][j] using dp[p][j-1] from previous j. So when computing dp[3][3], we need dp[p][2] for p in [max(1,3-k),2]. dp[2][2] would have been computed in the same j=2 loop? Actually j=2 is computed before j=3. So dp[2][2] is computed when j=2, then for j=3 we use dp[2][2] etc. So it works. For i=1, dp[1][1] valid. So eventually dp[n][n] computed. So answer for x=n is sum of all a_i.

    But what if we select all positions but first selected index is not 1? That would mean we skip 1, so we are not selecting all positions. So okay.

    Thus DP works.

    Now we might need to consider that we might have multiple ways; we take max.

    One nuance: Our DP assumes that we always have exactly j pictures up to i with i as the last selected. But it's possible that we have a valid selection of j pictures that ends before i but does not include i. That's not stored in dp[i][j], but we don't need that because at the end we only care about last selected.

    Thus solution is fine.

    Now confirm with other cases: For x less than min, DP would still try to compute but might not yield any valid ending. For example n=5,k=2,x=1. We computed dp[1][1]=5, dp[2][1]=1. Then answer from i>=4 none, so -1. So correct.

    Now complexity is O(n^2*x) = O(n^3) worst-case if x ~ n, about 8e6 for n=200, fine.

    We can also implement with prefix max for each j to reduce to O(n*x), but not necessary.

    Now we need to watch for overflow: Use long long.

    Implementation in C++:

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF = 1e18;
    
    int main() {
        int n, k, x;
        cin >> n >> k >> x;
        vector<ll> a(n+1);
        for (int i=1; i<=n; ++i) cin >> a[i];
        
        // optional feasibility check
        int min_required = ((n+1) + k - 1) / k - 1; // ceil((n+1)/k) - 1
        if (x < min_required) {
            cout << -1 << endl;
            return 0;
        }
        
        vector<vector<ll>> dp(n+1, vector<ll>(x+1, -INF));
        
        // initialize for j=1
        for (int i=1; i<=n; ++i) {
            if (i <= k) {
                dp[i][1] = a[i];
            }
        }
        
        // DP for j=2..x
        for (int j=2; j<=x; ++j) {
            for (int i=1; i<=n; ++i) {
                ll best = -INF;
                int start = max(1, i - k);
                for (int p=start; p < i; ++p) {
                    if (dp[p][j-1] > best) {
                        best = dp[p][j-1];
                    }
                }
                if (best != -INF) {
                    dp[i][j] = best + a[i];
                }
            }
        }
        
        ll ans = -INF;
        int left = max(1, n - k + 1);
        for (int i=left; i<=n; ++i) {
            if (dp[i][x] > ans) ans = dp[i][x];
        }
        
        if (ans == -INF) cout << -1 << endl;
        else cout << ans << endl;
        
        return 0;
    }
    

    But wait: The feasibility check may be slightly off? Let's derive min_required carefully.

    We need to ensure that there exists a set of x points with the condition. We argued any x >= m_min works. But is it always possible to select exactly x points for any x between m_min and n? Need to confirm. Since we can always add points, but must keep the start and end constraints. Adding points cannot violate those constraints if we add points within the existing range? But what if the existing first point is at position 1? Then we cannot add a point before it because there is none (positions start at 1). But we could add points after it, as long as we maintain gaps. However we might not be able to increase the count arbitrarily if all positions are already selected? But we only need to go up to n, and we can select all positions. So if x <= n, we can just select all positions, which is valid. So any x between m_min and n is achievable? Not exactly: Is selecting all positions always valid? Yes, because all pictures selected, so every segment has at least one. So any x = n is valid. But can we achieve any x between m_min and n? We can start from a minimal valid set (size m_min) and add extra points to reach x. But is it always possible to add exactly the required number of extra points without violating the condition? Since we can always add points