Submission #740560

#	Time	Username	Problem	Language	Result	Execution time	Memory
740560		ALVIN	Split the sequence (APIO14_sequence)	Pypy 3	0 / 100	41 ms	18228 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

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