oj.uz

Submission #740563

# Submission time Handle Problem Language Result Execution time Memory
740563 2023-05-12T17:25:07 Z ALVIN Split the sequence (APIO14_sequence) PyPy 3
0 / 100
 39 ms 18212 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
  
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.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 18124 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 39 ms 18188 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 36 ms 18212 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 39 ms 18148 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 34 ms 18156 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 34 ms 18204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -