1228 - SSK

Enunt

Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.

Cerinţa

Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din șirul ordonat al sumelor tuturor subtablourilor matricei A.

Date de intrare

Fișierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spațiu, având semnificația din enunț. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.

Date de ieșire

Fişierul de ieşire ssk.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.

Restricţii şi precizări

• 1 ≤ N ≤ 150
• 1 ≤ M ≤ 150
• 1 ≤ K ≤ numărul de termeni din şirul ordonat
• 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N și 1 ≤ j ≤ M

Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1.

Exemplu

ssk.in

2 3 14
3 2 7 
4 1 0 

ssk.out

9

Explicație

Șirul ordonat al tuturor sumelor subtablourilor matricei este

0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17

A patrusprezecea sumă este 9.

Rezolvare

def calculate_subtable_sums(matrix):
    n = len(matrix)
    m = len(matrix[0])

    # Initialize the cumulative sum matrix
    cumulative_sum = [[0] * (m + 1) for _ in range(n + 1)]

    # Calculate cumulative sum matrix
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cumulative_sum[i][j] = matrix[i - 1][j - 1] + cumulative_sum[i - 1][j] + cumulative_sum[i][j - 1] - cumulative_sum[i - 1][j - 1]

    # Calculate the sum of each subtable and store it in a list
    subtable_sums = []
    for i1 in range(1, n + 1):
        for j1 in range(1, m + 1):
            for i2 in range(i1, n + 1):
                for j2 in range(j1, m + 1):
                    subtable_sum = cumulative_sum[i2][j2] - cumulative_sum[i2][j1 - 1] - cumulative_sum[i1 - 1][j2] + cumulative_sum[i1 - 1][j1 - 1]
                    subtable_sums.append(subtable_sum)

    # Sort the list of subtable sums
    subtable_sums.sort()
    
    return subtable_sums

def main():
    with open("ssk.in", "r") as fin:
        N, M, K = map(int, fin.readline().split())
        matrix = [list(map(int, fin.readline().split())) for _ in range(N)]

    # Calculate subtable sums
    subtable_sums = calculate_subtable_sums(matrix)

    # Retrieve the K-th term
    kth_term = subtable_sums[K - 1]

    # Write the result to the output file
    with open("ssk.out", "w") as fout:
        fout.write(str(kth_term) + "\n")

if __name__ == "__main__":
    main()