1498 - Ciocolata

Enunț

După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul).

Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii și M coloane pe care îl umple cu valori întregi. Cristina va primi un număr de pătrățele de ciocolată egal cu suma valorilor dintr-un dreptunghi ales de ea.”

Deoarece Cristina este prea bosumflată ca să rezolve această “provocare” și prea obosită ca să-l convingă pe Dan să-i dea ciocolata pur și simplu, vă roagă pe voi să o ajutați. (Poate primiți și voi niște ciocolată dacă rezolvați problema. Poate…)

Cerința

Cunoscându-se configurația caroiajului, determinați numărul maxim de pătrățele de ciocolată pe care Cristina îl poate obține alegând un dreptunghi din matrice, precum și coordonatele celor patru colțuri ale acestuia

Date de intrare

Fișierul ciocolatain.txt conține pe prima linie două numere naturale N și M reprezentând numărul de linii și numărul de coloane ale caroiajului. Pe următoarele N linii se găsesc câte M valori întregi reprezentând valorile din caroiaj.

Date de ieșire

Fisierul ciocolataout.txt va conține pe prima linie numărul maxim de pătrățele de ciocolată care se poate obține. Pe a doua linie se vor afla patru numere naturale reprezentând coordonatele colțurilor stânga- sus și dreapta-sus (în această ordine) a dreptunghiului ales. Pe cea de-a treia linie se vor afla tot patru numere naturale reprezentând coordonatele colțurilor stânga-jos și dreapta-jos (în această ordine) a dreptunghiului ales.

Restricții și precizări

• 1 ≤ N, M ≤ 500
• Valorile din caroiaj aparțin intervalului [ -2.000.000.000 , 2.000.000.000 ]
• În cazul în care există mai multe dreptunghiuri din care se obține aceeași valoare maximă, se va alege cel cu indicele de linie al colțului stânga-sus minim. În cazul în care există mai multe dreptunghiuri cu această proprietate, se va alege cel ce are și indicele de coloană al colțului stânga-sus minim. Dacă există mai multe soluții cu proprietatea că au colțul stânga-sus cu indicii de linie și de coloană minimi, se va alege cel cu indicele de linie al coltului dreapta-jos minim. Dacă mai rămân soluții multiple, se va alege cel care are și indicele de coloană al colțului dreapta-jos minim.
• (schematic: valoare maximă → indice linie stânga-sus minim → indice coloană stânga-sus minim → indice linie dreapta-jos minim → indice coloană dreapta-jos minim )
• Se garantează că nici Cristinei și nici lui Dan nu li se va face rău de la ciocolată.

Exemplu:

ciocolatain.txt

5 9

3 4 -12 4 6 7 -9 5 12

0 4 5 7 9 -5 1 1 5

0 98 34 0 1 7 -7 1 1

6 7 8 -9 0 -2 3 5 22

47 62 -31 55 0 -83 23 77 -10

ciocolataout.txt

362

1 1 1 9

5 1 5 9

Explicație

Dreptunghiul determinat de punctele (1, 1), (1, 9), (5, 1), (5, 9).

Rezolvare

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)