Submission #1116318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116318		tjgus1668	Split the sequence (APIO14_sequence)	Cpython 3	28 / 100	2057 ms	52032 KiB

sequence

lines = list[tuple[int, int, int]]()

def inter(a, b):
    return (lines[a][1] - lines[b][1]) / (lines[b][0] - lines[a][0])

def add(a, b, idx):
    lines.append((a, b, idx))
    while len(lines) > 2 and inter(-1, -2) < inter(-2, -3): lines.pop(-2)

def get(x):
    s, e = 0, len(lines) - 1
    while s < e:
        m = s + e >> 1
        if inter(m, m + 1) < x: s = m + 1
        else: e = m
    return e

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
for i in range(1, N + 1): A[i] += A[i - 1]

dp = [[0] * (N + 1) for _ in range(K + 1)]
# dp = [[[0, 0] for _ in range(N + 1)] for _ in range(K + 1)]
pre = [[0] * (N + 1) for _ in range(K + 1)]

for k in range(1, K + 1):
    lines.clear()
    add(A[1], dp[k - 1][0] - A[1] ** 2, 1)
    for i in range(2, N + 1):
        j = get(A[i])
        dp[k][i] = A[i] * A[lines[j][2]] + dp[k - 1][lines[j][2]] - A[lines[j][2]] ** 2
        pre[k][i] = lines[j][2]
        if A[i] - A[i - 1] == 0: continue
        add(A[i], dp[k - 1][i] - A[i] ** 2, i)
    # for i in range(1, N + 1):
        # dp[k][i] = max(dp[k - 1][j] + A[j] * (A[i] - A[j]) for j in range(i))
        # dp[k][i] = max(A[i] * A[j] + dp[k - 1][j] - A[j] ** 2 for j in range(i))
        # for j in range(i):
        #     if dp[k - 1][j] + A[j] * (A[i] - A[j]) > dp[k][i]:
        #         dp[k][i] = dp[k - 1][j] + A[j] * (A[i] - A[j])
        #         pre[k][i] = j
        #     if dp[k - 1][j][0] + A[j] * (A[i] - A[j]) > dp[k][i][0]:
        #         dp[k][i][0] = dp[k - 1][j][0] + A[j] * (A[i] - A[j])
        #         dp[k][i][1] = j

p = dp[K].index(max(dp[K]))
ans = []
for k in range(K, 0, -1):
    p = pre[k][p]
    ans.append(p)
print(max(dp[K]))
print(*ans[::-1])

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