Problem p03326 (python)

Fixed submission:
from itertools import product

N, M = [int(elem) for elem in input().split(' ')]
coord_list = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(coord_list) == N
assert len(coord_list[0]) == 3

max_total = 0
for f_x, f_y, f_z in product([-1, 1], repeat=3):
    sum_list = [(f_x * x + f_y * y + f_z * z, i) for i, (x, y, z) in enumerate(coord_list)]
    # sort with index
    sum_list = sorted(sum_list, key=lambda x: x[0])[::-1]
    total_x, total_y, total_z = 0, 0, 0
    for _, idx in sum_list[:M]:
        total_x += coord_list[idx][0]
        total_y += coord_list[idx][1]
        total_z += coord_list[idx][2]
    total = abs(total_x) + abs(total_y) + abs(total_z)
    max_total = max(total, max_total)

print(max_total)

Buggy submission (verdict: Runtime Error):
N, M = [int(elem) for elem in input().split(' ')]
coord_list = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(coord_list) == N
assert len(coord_list[0]) == 3


def search_max(sorted_coord_list, M, key):
    len_list = len(sorted_coord_list)
    if M == len_list:
        total_x, total_y, total_z = 0, 0, 0
        for x, y, z in sorted_coord_list:
            total_x += x
            total_y += y
            total_z += z
        total = abs(total_x) + abs(total_y) + abs(total_z)
        return total

    elif M == 1:
        x, y, z = sorted_coord_list[0]
        total = abs(x) + abs(y) + abs(z)
        return total

    # 2 <= M < N
    else:
        if sorted_coord_list[M - 1][key] == sorted_coord_list[M][key]:
            considering_val = coord_list[M - 1][key]
            current_idx = M - 1
            candidate_list = list()
            while (coord_list[current_idx][key] == considering_val) or (current_idx != len_list):
                candidate_list.append(sorted_coord_list[current_idx])
                current_idx += 1
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M - 1]:
                total_x += x
                total_y += y
                total_z += z
            max_total = 0
            for x, y, z in candidate_list:
                total = abs(total_x + x) + abs(total_y + y) + abs(total_z + z)
                max_total = max(max_total, total)
            return max_total

        else:
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M]:
                total_x += x
                total_y += y
                total_z += z
            total = abs(total_x) + abs(total_y) + abs(total_z)
            return total


max_candidates = [0] * 6
for i in range(3):
    # sort coord_list: O(NlogN)
    sorted_coord_list = sorted(coord_list, key=lambda x: x[i])
    max_candidates[2 * i] = search_max(sorted_coord_list, M, i)
    max_candidates[2 * i + 1] = search_max(sorted_coord_list[::-1], M, i)

print(max(max_candidates))

Buggy submission (verdict: Runtime Error):
N, M = [int(elem) for elem in input().split(' ')]
coord_list = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(coord_list) == N
assert len(coord_list[0]) == 3


def search_max(sorted_coord_list, M, key):
    len_list = len(sorted_coord_list)
    if M == len_list:
        total_x, total_y, total_z = 0, 0, 0
        for x, y, z in sorted_coord_list:
            total_x += x
            total_y += y
            total_z += z
        total = abs(total_x) + abs(total_y) + abs(total_z)
        return total

    elif M == 1:
        x, y, z = sorted_coord_list[0]
        total = abs(x) + abs(y) + abs(z)
        return total

    # 2 <= M < N
    else:
        if sorted_coord_list[M - 1][key] == sorted_coord_list[M][key]:
            considering_val = coord_list[M - 1][key]
            current_idx = M - 1
            candidate_list = list()
            while (coord_list[current_idx][key] == considering_val) or current_idx == len_list:
                candidate_list.append(sorted_coord_list[current_idx])
                current_idx += 1
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M - 1]:
                total_x += x
                total_y += y
                total_z += z
            max_total = 0
            for x, y, z in candidate_list:
                total = abs(total_x + x) + abs(total_y + y) + abs(total_z + z)
                max_total = max(max_total, total)
            return max_total

        else:
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M]:
                total_x += x
                total_y += y
                total_z += z
            total = abs(total_x) + abs(total_y) + abs(total_z)
            return total


max_candidates = [0] * 6
for i in range(3):
    # sort coord_list: O(NlogN)
    sorted_coord_list = sorted(coord_list, key=lambda x: x[i])
    max_candidates[2 * i] = search_max(sorted_coord_list, M, i)
    max_candidates[2 * i + 1] = search_max(sorted_coord_list[::-1], M, i)

print(max(max_candidates))

Buggy submission (verdict: Runtime Error):
N, M = [int(elem) for elem in input().split(' ')]
coord_list = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(coord_list) == N
assert len(coord_list[0]) == 3

def search_max(sorted_coord_list, M, key):
    len_list = len(sorted_coord_list)
    if M == len_list:
        total_x, total_y, total_z = 0, 0, 0
        for x, y, z in sorted_coord_list:
            total_x += x
            total_y += y
            total_z += z
        total = abs(total_x) + abs(total_y) + abs(total_z)
        return total
    elif M == 1:
        x, y, z = sorted_coord_list[0]
        total = abs(x) + abs(y) + abs(z)
        return total
        
    # 2 <= M < N
    else:
        if sorted_coord_list[M - 1][key] == sorted_coord_list[M][key]:
            considering_val = coord_list[M - 1][key]
            current_idx = M - 1
            candidate_list = list()
            while coord_list[current_idx][key] == considering_val:
                candidate_list.append(sorted_coord_list[current_idx])
                current_idx += 1
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M - 1]:
                total_x += x
                total_y += y
                total_z += z
            max_total = 0
            for x, y, z in candidate_list:
                total = abs(total_x + x) + abs(total_y + y) + abs(total_z + z)
                max_total = max(max_total, total)
            return max_total
    
        else:
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M]:
                total_x += x
                total_y += y
                total_z += z
            total = abs(total_x) + abs(total_y) + abs(total_z)
            return total


max_candidates = [0] * 6
for i in range(3):
    # sort coord_list: O(NlogN)
    sorted_coord_list = sorted(coord_list, key=lambda x: x[i])
    max_candidates[2 * i] = search_max(sorted_coord_list, M, i)
    max_candidates[2 * i + 1] = search_max(sorted_coord_list[::-1], M, i)

print(max(max_candidates))

Buggy submission (verdict: Runtime Error):
N, M = [int(elem) for elem in input().split(' ')]
coord_list = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(coord_list) == N
assert len(coord_list[0]) == 3

def search_max(sorted_coord_list, M, key):
    len_list = len(sorted_coord_list)
    if M == len_list:
        total_x, total_y, total_z = 0, 0, 0
        for x, y, z in sorted_coord_list:
            total_x += x
            total_y += y
            total_z += z
        total = abs(total_x) + abs(total_y) + abs(total_z)
        return total
    elif M == 1:
        x, y, z = sorted_coord_list[0]
        total = abs(x) + abs(y) + abs(z)
        return total
        
    else:
        if sorted_coord_list[M - 1][key] == sorted_coord_list[M][key]:
            considering_val = coord_list[M - 1][key]
            current_idx = M - 1
            candidate_list = list()
            while coord_list[current_idx][key] == considering_val:
                candidate_list.append(sorted_coord_list[current_idx])
                current_idx += 1
            total_x, total_y, total_z = 0, 0, 0
            for x, y, z in sorted_coord_list[:M-1]:
                total_x += x
                total_y += y
                total_z += z

            max_total = 0
            for x, y, z in candidate_list:
                total = abs(total_x + x) + abs(total_y + y) + abs(total_z + z)
                max_total = max(max_total, total)
            return max_total
    
        else:
            total_x, total_y, total_z = 0, 0, 0
        for x, y, z in sorted_coord_list[:M]:
            total_x += x
            total_y += y
            total_z += z
        total = abs(total_x) + abs(total_y) + abs(total_z)
        return total


max_candidates = [0] * 6
for i in range(3):
    # sort coord_list: O(NlogN)
    sorted_coord_list = sorted(coord_list, key=lambda x: x[i])
    max_candidates[2 * i] = search_max(sorted_coord_list, M, i)
    max_candidates[2 * i + 1] = search_max(sorted_coord_list[::-1], M, i)

print(max(max_candidates))