oj.uz

Submission #740560

# Submission time Handle Problem Language Result Execution time Memory
740560 2023-05-12T17:21:36 Z ALVIN Split the sequence (APIO14_sequence) PyPy 3
0 / 100
 41 ms 18228 KB 
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 18228 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 18184 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 18164 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 18220 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 18140 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 18144 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -