Submission #669922

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

sequence

import sys
from collections import deque
input = sys.stdin.readline

class linearFunc():
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.s = 0
        self.num = 0
    
def intersect(L1, L2):
    return (L2.b-L1.b)/(L1.a-L2.a)

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(linearFunc(0, int(-1e14)))
    for i in range(k+1, N):
        g = linearFunc(psum[i-1], DP[(k%2)^1][i-1]-(psum[i-1])**2)
        g.num = i-1
        if F[-1].a == g.a and F[-1].b < g.b:
            F.pop()
            while F:
                g.s = intersect(F[-1], g)
                if F[-1].s < g.s: break
                F.pop()
            if g.s <= psum[-1]: F.append(g)

        elif F[-1].a != g.a or (F[-1].a == g.a and F[-1].b < g.b):
            while F:
                g.s = intersect(F[-1], g)
                if F[-1].s < g.s: break
                F.pop()
            F.append(g)

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

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