# PBinfo #1515 – gradina – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Enunț
Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de N metri unde, pe vremuri,  fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de K metri. 

Cerința
Cunoscând dimensiunile livezii și grădinii, numărul pomilor din livadă și poziția fiecăruia, determinați numărul maxim de pomi dintr-o grădină pătrată de latură K și numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi. 

Date de intrare
Fișierul gradina.in conține: 


pe prima linie numerele naturale N, P și K, separate prin câte un spațiu, cu semnificaţia din enunţ;
pe următoarele P linii câte 2 numere naturale Lin și Col, separate printr-un spațiu, reprezentând numărul rândului, respectiv poziția în rând a fiecărui pom din livadă.

Date de ieșire
Fișierul gradina.out va conține: 


pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri;
pe a doua linie numărul de posibilități de a amplasa grădina astfel încât să conțină numărul maxim de pomi determinat.

Restricții și precizări

2 ≤ N ≤ 1000
1 ≤ P ≤ N*N
1 ≤ K ≤ N

Exemplu:
gradina.in

12 10 5 
4 3 
5 5 
6 8 
7 3 
7 7 
8 8 
9 3 
9 6 
10 10 
11 5
gradina.out

5
5
Explicație
Grădina lui Păcală poate avea maximum 5 pomi fructiferi. Ea poate fi amplasată în 5 moduri, având colțul stânga-sus de coordonate: (5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("gradina.in");
ofstream out("gradina.out");
#define cin in
#define cout out
int n, p, k, mat[1001][1001];
long long int S[1005][1005];
long long int maxim = -1, contor = 0;
int main() {
    cin >> n >> p >> k;
    for (int i = 0; i <= n; i++)
        S[i][0] = 0;
    for (int j = 0; j <= n; j++)
        S[0][j] = 0;
    for (int i = 1; i <= p; i++) {
        int lin, col;
        cin >> lin >> col;
        mat[lin][col] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
                S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + mat[i][j];
    for (int i = k; i <= n; i++)
        for (int j = k; j <= n; j++) {
                long long int suma = S[i][j] - S[i - k][j] - S[i][j - k] + S[i - k][j - k];
                if (suma > maxim)
                    maxim = suma, contor = 1;
                else if (suma == maxim)
                    contor++;
        }
    cout << maxim << "\n";
    cout << contor;  
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1515)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1515/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1515/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)