# PBinfo #3686 – Vaccination – Rezolvare C++

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

## Enunț

Cerința
Echipa V.R.N.C. a dezvoltat un vaccin contra celei mai recente boli. Vaccinul este distribuit mai întâi unei singure persoane, iar mai apoi se împrăștie celor 4 vecini(populația este reprezentată pe o matrice de dimensiunile n și m). Ulterior, fiecare persoana va da vaccinul celor 4 vecini până când o persoană de la marginea matricii este vaccinată, moment în care vaccinul nu mai este dat mai departe. 

Vazând succesul acestei metode, V.R.N.C ne dă o matrice în care știm vârsta fiecărei persoane și trebuie să aflăm punctul unde V.R.N.C ar trebui să înceapă distribuția vaccinului astfel încât să maximizăm suma vârstelor oamenilor vaccinați.

Date de intrare
Programul citește de la tastatură pe prima linie numerele n și m, iar apoi n linii, fiecare linie conținând m numere separate prin spații, reprezentând vârstele celor n*m cetățeni. 

Date de ieșire
Programul va afișa pe ecran două valori i și j, locul unde vaccinarea ar trebui să înceapă. Dacă sunt mai multe soluții, trebuie afișată cea mai din stânga-sus poziție. 

Restricții și precizări

1 ≤ n, m ≤ 1000
cele n*m numere citite vor fi între 0 și 2147483647

Exemplu:
Intrare

3 4
1 2 3 4
5 6 7 8
9 10 11 12
Ieșire

2 3
Explicație
Începând de la celula (2, 3) cu valoarea 7, vaccinul va ajunge și la valorile 3, 6, 8 și 11, suma fiind 35, aceasta fiind suma maximă posibilă obținută.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> v(n+3, vector<int> (m+3, 0));
	auto pr = v;
	auto diagleft = v;
	auto diagright = v;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> v[i][j];
	for (int i = n; i >= 1; --i) {
		for (int j = 1; j <= m+1; ++j) {
			diagleft[i][j] = diagleft[i+1][j-1] + v[i][j];
			diagright[i][j] = diagright[i+1][j+1] + v[i][j];
		}
		diagright[i][0] = diagright[i+1][1] + v[i][0];
	}
	for (int i = n; i >= 1; --i) {
		for (int j = 2; j < m; ++j)
			pr[i][j] = pr[i+1][j-1] + pr[i+1][j+1] - pr[i+2][j] + v[i][j] + v[i+1][j]; 
		pr[i][1] = pr[i+1][1] + diagright[i][1];
		pr[i][m] = pr[i+1][m] + diagleft[i][m];
	}
	int mx = -1, I = -1, J = -1;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			int d = min(i-1, j-1);
			d = min(d, n-i);
			d = min(d, m-j);
			int sum = pr[i-d][j] - pr[i+1][j-d] - pr[i+1][j+d] + pr[i+d+1][j] - diagleft[i+1][j-d-1] - diagright[i+1][j+d+1];
			if (sum > mx) {
				mx = sum;
				I = i;
				J = j;
			}
		}
	cout << I << " " << J << "\n";
	return 0;
}
```

## Resurse

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