Editing 2353 - Padure

Într-o pădure există plantați copaci pe <code>N</code> linii și <code>M</code> coloane. Copacii au diferite înălțimi. O zonă dreptunghiulară de copaci din cadrul pădurii trebuie tăiată. Pădurarul trebuie să aleagă dintre <code>C</code> zone, o zonă în care suma înălțimilor copacilor este maximă. Deoarece pădurarului îi plac numerele prime, el va alege o zonă în care suma înălțimilor copacilor este și un număr prim.

= Cerința =
Determinați suma din enunț pentru zonele puse la dispoziție.

= Date de intrare =
Fișierul de intrare <code>padure.in</code> conţine pe prima linie numerele <code>N</code>, <code>M</code> și <code>C</code> cu semnificația din enunț, pe următoarele <code>N</code> linii înălțimile copacilor, câte <code>M</code> pe o linie, separate prin câte un spațiu, iar pe următoarele <code>C</code> linii, câte patru pe fiecare linie,  valorile <code>l1</code>, <code>c1</code>, <code>l2</code>, <code>c2</code> separate prin câte un spațiu, ce reprezintă coordonatele colțului stânga-sus, respectiv coordonatele colțului dreapta-jos a unei zone ce poate fi tăiată.

= Date de ieșire =
Fișierul de ieșire <code>padure.out</code> va conţine pe prima linie rezultatul corespunzător cerinței problemei.

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 100</code>
* <code>1 ≤ C ≤ 100.000</code>
* numerotarea liniilor și coloanelor din pădure începe de la <code>1</code>
* <code>0 < l1 ≤ l2 ≤ N</code>
* <code>0 < c1 ≤ c2 ≤ M</code>
* pentru fiecare set de date de intrare există soluție
* înălțimea copacilor nu depășește valoarea <code>100</code>

= Exemplu: =
<code>padure.in</code>
 4 4 2
 9 3 2 4
 6 2 1 5
 2 3 2 4
 4 5 3 4
 1 1 3 3
 2 2 4 4
<code>padure.out</code>
 29

=== Explicație ===
<code>9 3 2</code>

<code>6 2 1</code>

<code>2 3 2</code>

are suma <code>30</code>, dar nu este prim

<code>2 1 5</code>

<code>3 2 4</code>

<code>5 3 4</code>

are suma <code>29</code>

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import math

n, m, k = map(int, input().split())
A = [[0] * (m + 1) for _ in range(n + 1)]
S = [[0] * (m + 1) for _ in range(n + 1)]
smax = -200000000

def prim(n):
    if n == 0 or n == 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

for i in range(1, n + 1):
    for j in range(1, m + 1):
        A[i][j] = int(input())

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

for _ in range(k):
    i1, j1, i2, j2 = map(int, input().split())
    s = S[i2][j2] - S[i1 - 1][j2] - S[i2][j1 - 1] + S[i1 - 1][j1 - 1]
    if s > smax and prim(s):
        smax = s

print(smax)


</syntaxhighlight>