oj.uz

답안 #851636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851636 2023-09-20T09:53:25 Z tester777 수열 (APIO14_sequence) Python 3
0 / 100
 2000 ms 16256 KB 
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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 2908 KB declared answer doesn't correspond to the split scheme: declared = 17, real = 107
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 2908 KB declared answer doesn't correspond to the split scheme: declared = 10109, real = 80828
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 2908 KB declared answer doesn't correspond to the split scheme: declared = 40353, real = 282432
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 585 ms 3448 KB declared answer doesn't correspond to the split scheme: declared = 12015, real = 144068
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2103 ms 4760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2037 ms 16256 KB Time limit exceeded
2 Halted 0 ms 0 KB -