Submission #851636

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
851636	2023-09-20 09:53:25	tester777	Split the sequence (APIO14_sequence)	Cpython 3	0 / 100	2103 ms	16256 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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