2353 - Padure

Într-o pădure există plantați copaci pe N linii și M 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 C 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 padure.in conţine pe prima linie numerele N, M și C cu semnificația din enunț, pe următoarele N linii înălțimile copacilor, câte M pe o linie, separate prin câte un spațiu, iar pe următoarele C linii, câte patru pe fiecare linie, valorile l1, c1, l2, c2 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 padure.out va conţine pe prima linie rezultatul corespunzător cerinței problemei.

Restricții și precizări

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

Exemplu:

padure.in

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

padure.out

29

Explicație

9 3 2

6 2 1

2 3 2

are suma 30, dar nu este prim

2 1 5

3 2 4

5 3 4

are suma 29

Î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>