Submission #740563

#	Time	Username	Problem	Language	Result	Execution time	Memory
740563		ALVIN	Split the sequence (APIO14_sequence)	Pypy 3	0 / 100	39 ms	18212 KiB

sequence

def max_points(n, k, arr):
    dp = [[0 for _ in range(n+1)] for _ in range(k+1)]
    pref = [0 for _ in range(n+1)]
    track = [[0 for _ in range(n+1)] for _ in range(k+1)]
    
    for i in range(1, n+1):
        pref[i] = pref[i-1] + arr[i-1]
        
    for i in range(1, n+1):
        dp[1][i] = pref[i]*pref[n] - pref[i]*pref[i-1]
        track[1][i] = 0
        
    for i in range(2, k+1):
        mx = [(dp[i-1][j] + pref[j]*pref[i-1] - pref[j]*pref[j-1], j) for j in range(i-1)]
        for j in range(i, n+1):
            mx[0] = max(mx[0], (dp[i-1][j-1] + pref[j-1]*pref[n] - pref[j-1]*pref[j-2], j-1))
            dp[i][j], track[i][j] = mx[0]
            
    res = [0]*k
    cur = n
    for i in range(k, 0, -1):
        res[i-1] = track[i][cur]
        cur = res[i-1]
        
    return dp[k][n], res
  
def read_input(filename):
    with open(filename, 'r') as file:
        n, k = map(int, file.readline().split())
        arr = list(map(int, file.readline().split()))
    return n, k, arr
 
def write_output(filename, points, positions):
    with open(filename, 'w') as file:
        file.write(str(points) + '\n')
        file.write(' '.join(map(str, [pos+1 for pos in positions])) + '\n')

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