Editing 1498 - Ciocolata (section)

== Rezolvare ==
<syntaxhighlight lang="python">
def is_valid_input(n, m, a):
    if not (1 <= n <= 500) or not (1 <= m <= 500):
        return False

    for i in range(n):
        for j in range(m):
            if not (-2_000_000_000 <= a[i][j] <= 2_000_000_000):
                return False

    return True


def citeste_input(file_name="ciocolatain.txt"):
    with open(file_name, "r") as file:
        n, m = map(int, file.readline().split())
        a = [list(map(int, file.readline().split())) for _ in range(n)]

    if not is_valid_input(n, m, a):
        raise ValueError("Input invalid")

    return n, m, a


def scrie_output(smax, x1, y1, lx, ly, file_name="ciocolataout.txt"):
    with open(file_name, "w") as file:
        file.write(f"{smax}\n")
        file.write(f"{x1} {y1} {x1} {y1 + ly}\n")
        file.write(f"{x1 + lx} {y1} {x1 + lx} {y1 + ly}\n")


def gaseste_subsir_maxim(n, m, a):
    s = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            s[i][j] = a[i - 1][j - 1] + s[i - 1][j]

    smax, x1, y1, lx, ly = 0, 0, 0, 0, 0

    for p in range(1, n + 1):
        for q in range(p, n + 1):
            sum_val = 0
            lasty = 1
            for j in range(1, m + 1):
                s1 = s[q][j] - s[p - 1][j]
                sum_val += s1
                if sum_val < 0:
                    sum_val = 0
                    lasty = j + 1
                if sum_val > smax or (sum_val == smax and (p < x1 or (p == x1 and lasty < y1))):
                    smax = sum_val
                    x1 = p
                    y1 = lasty
                    lx = q - p
                    ly = j - lasty

    return smax, x1, y1, lx, ly


if __name__ == "__main__":
    n, m, a = citeste_input()
    smax, x1, y1, lx, ly = gaseste_subsir_maxim(n, m, a)
    scrie_output(smax, x1, y1, lx, ly)
</syntaxhighlight>