Submission #851636

#	Time	Username	Problem	Language	Result	Execution time	Memory
851636		tester777	Split the sequence (APIO14_sequence)	Cpython 3	0 / 100	2103 ms	16256 KiB

sequence

import sys

# Read input from stdin
n, k = map(int, input().split())
sequence = list(map(int, input().split()))

# Initialize a table to store the maximum total points for each subproblem
dp = [[0] * (n + 1) for _ in range(k + 2)]

# Initialize a table to store the split positions
split_positions = [[0] * (n + 1) for _ in range(k + 2)]

# Calculate the prefix sum of the sequence for quick sum calculations
prefix_sum = [0]
for num in sequence:
    prefix_sum.append(prefix_sum[-1] + num)

# Dynamic programming loop
for i in range(1, k + 2):
    for j in range(i, n + 1):
        dp[i][j] = float('-inf')
        for x in range(i - 1, j):
            current_points = dp[i - 1][x] + (prefix_sum[j] - prefix_sum[x])
            if current_points > dp[i][j]:
                dp[i][j] = current_points
                split_positions[i][j] = x

# Backtrack to find split positions
split_indices = []
i, j = k + 1, n
while i > 1:
    split_indices.append(split_positions[i][j] + 1)
    j = split_positions[i][j]
    i -= 1

# Print the maximum total points and split positions to stdout
print(dp[k + 1][n])
print(*split_indices)

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29