Submission #669934

#	Time	Username	Problem	Language	Result	Execution time	Memory
669934		yyhjin12	Split the sequence (APIO14_sequence)	Pypy 3	71 / 100	570 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 = [0]*N; F[0] = linearFunc(0, int(-1e14)); top = 1; idx = 0
    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[top-1].a == g.a and F[top-1].b < g.b:
            top -= 1
            while top>0:
                g.s = intersect(F[top-1], g)
                if F[top-1].s < g.s: break
                top -= 1
            if g.s <= psum[-1]: F[top] = g; top += 1

        elif F[top-1].a != g.a or (F[top-1].a == g.a and F[top-1].b < g.b):
            while top>0:
                g.s = intersect(F[top-1], g)
                if F[top-1].s < g.s: break
                top -= 1
            F[top] = g; top += 1

        X = psum[i]
        while idx+1<top and F[idx+1].s < X: idx += 1
        DP[k%2][i] = F[idx].a * X + F[idx].b
        prev[k][i] = F[idx].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