Submission #669970

#	Time	Username	Problem	Language	Result	Execution time	Memory
669970		yyhjin12	Split the sequence (APIO14_sequence)	Pypy 3	71 / 100	434 ms	131072 KiB

sequence

import sys
from collections import deque
input = sys.stdin.readline
    
def intersect(L1, L2):
    return (L2[1]-L1[1])/(L1[0]-L2[0])

N, K = map(int, input().split())
psum = list(map(int, input().split()))

#Prefix Sum
for i in range(1, N): psum[i] += psum[i-1]

#Initialize DP Table
prev = [[0]*N for _ in range(K)]
DP = [[0]*N for _ in range(2)]

for k in range(K):
    F = deque(); F.append((0, int(-1e14), -1, -1))
    for i in range(k+1, N):
        g = (psum[i-1], DP[(k%2)^1][i-1]-psum[i-1]*psum[i-1], 0, i-1)
        if F[-1][0] == g[0] and F[-1][1] < g[1]:
            F.pop()
            while F:
                g = (g[0], g[1], intersect(F[-1], g), g[3])
                if F[-1][2] < g[2]: break
                F.pop()
            F.append(g)

        elif F[-1][0] != g[0] or (F[-1][0] == g[0] and F[-1][1] < g[1]):
            while F:
                g = (g[0], g[1], intersect(F[-1], g), g[3])
                if F[-1][2] < g[2]: break
                F.pop()
            F.append(g)

        X = psum[i]
        while len(F)>1 and F[1][2] < X: F.popleft()
        DP[k%2][i] = F[0][0] * X + F[0][1]
        prev[k][i] = F[0][3]

print(DP[(K-1)%2][N-1])

temp = N-1; q = K-1; L = []
while q>=0:
    L.append(prev[q][temp]+1)
    temp = prev[q][temp]; q -= 1
L.sort()
print(' '.join(map(str, L)))

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