Editing 3438 - Triunghi 5

Se consideră <code>A</code> un tablou bidimensional cu <code>n</code> linii, <code>n</code> coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul <code>(lin, col, k)</code>, este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu <code>|k|</code>, definită astfel:

# Pentru <code>k>0</code>, zona este compusă din <code>k</code> linii:
#* pe prima linie a zonei se află elementele <code>A[lin][col]</code>, <code>A[lin][col+1]</code>, …, <code>A[lin][col+k-1]</code>;
#* pe a doua linie a zonei se află elementele <code>A[lin+1][col]</code>, <code>A[lin+1][col+1]</code>, …, <code>A[lin+1][col+k-2]</code>;
#* pe a treia linie a zonei se află elementele <code>A[lin+2][col]</code>, <code>A[lin+2][col+1]</code>, …, <code>A[lin+2][col+k-3]</code>;
#* …
#* pe ultima linie a zonei se află elementul <code>A[lin+k-1][col]</code>.
# Pentru <code>k<0</code>, zona este compusă din <code>|k|=-k</code> linii:
#* pe prima linie a zonei se află elementul <code>A[lin-|k|+1][col]</code>;
#* pe a doua linie a zonei se află elementele <code>A[lin-|k|+2][col-1]</code>, <code>A[lin-|k|+2][col]</code>;
#* …
#* pe ultima linie a zonei se află elementele <code>A[lin][col-|k|+1]</code>, <code>A[lin][col-|k|+2]</code>,…, <code>A[lin][col]</code>.

Suma elementelor ce compun o zonă triunghiulară se numește suma zonei.

= Cerința =
Scrieţi un program care, cunoscând tabloul <code>A</code> şi <code>Q</code> zone triunghiulare, determină cea mai mare dintre sumele zonelor.

= Date de intrare =
Fișierul de intrare <code>triunghi.in</code> conține pe prima linie numărul natural <code>n</code>, cu semnificaţia din enunţ. Pe următoarele <code>n</code> linii se găsesc câte n valori naturale, reprezentând elementele tabloului <code>A</code>. Pe linia <code>n+2</code> se află numărul natural <code>Q</code>, reprezentând numărul zonelor triunghiulare. Pe următoarele <code>Q</code> linii se găsesc tripletele de valori <code>lin col k</code>, care reprezintă cele <code>Q</code> zone, în forma descrisă în enunţ. Valorile aflate pe aceeaşi linie a fişierului sunt separate prin câte un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>triunghi.out</code> va conține o singură linie pe care va fi scris un număr natural reprezentând suma maximă cerută.

= Restricții și precizări =

* <code>3 ≤ n ≤ 1000</code>; <code>1 ≤ Q ≤ 100000</code>; <code>2 ≤ |k| ≤ n</code>
* Valorile din tablou sunt numere naturale din intervalul <code>[1,100]</code>.
* Liniile şi coloanele tabloului <code>A</code> sunt numerotate de la <code>1</code> la <code>n</code> (liniile de sus în jos, iar coloanele de la stânga la dreapta).
* <code>|k|</code> reprezintă modulul numărului <code>k</code> (<code>k</code>, pentru <code>k≥0</code>, respectiv <code>-k</code>, pentru <code>k<0</code>).
* Se garantează că orice zonă triunghiulară dintre cele <code>Q</code> este complet inclusă în tabloul <code>A</code>.

= Exemplu: =
<code>triunghi.in</code>
 6
 5 8 10 4 9 4
 2 10 10 2 4 8
 8 10 3 4 6 6
 4 6 9 7 1 9
 6 7 2 2 10 6
 10 4 6 1 10 4
 3
 4 1 3
 4 4 -4
 6 5 -2
<code>triunghi.out</code>
 59

=== Explicație ===
Zona triunghiulară de sumă maximă (<code>59</code>) este reprezentată de tripletul <code>(4 4 -4)</code> și conține

valorile evienţiate: <code>59=4+(10+2)+(10+3+4)+(4+6+9+7)</code>.

<syntaxhighlight lang="python" line="1">
def suma_zona_triunghiulara(A, lin, col, k):
    suma = 0
    n = len(A)
    
    if k > 0:
        # Zona triunghiulară pentru k > 0
        for i in range(k):
            for j in range(k - i):
                suma += A[lin + i][col + j]
    else:
        # Zona triunghiulară pentru k < 0
        k = -k
        for i in range(k):
            for j in range(i + 1):
                suma += A[lin - i + (k - 1)][col - j + (k - 1)]
    
    return suma

def cea_mai_mare_suma(A, interogari):
    max_suma = float('-inf')
    
    for (lin, col, k) in interogari:
        suma = suma_zona_triunghiulara(A, lin, col, k)
        if suma > max_suma:
            max_suma = suma
    
    return max_suma

# Citire date
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
Q = int(input())
interogari = [tuple(map(int, input().split())) for _ in range(Q)]

# Calculare cea mai mare sumă
result = cea_mai_mare_suma(A, interogari)
print(result)
</syntaxhighlight>