![]() |
OLIMPIADA DE INFORMATICA Etapa municipala IASI, 20 ianuarie 2007 |
Clasa a X a |
Problema 1 - ture
100 puncte
Sa consideram o matrice cu N linii si N coloane cu elemente numere naturale. In aceasta matrice trebuie sa plasam doua ture, īn pozitii distincte. Spunem ca un element al matricei este atacat daca se afla pe aceeasi linie sau pe aceeasi coloana cu una dintre cele doua ture. Elementele din pozitiile celor doua ture nu sunt considerate atacate. Turele vor fi plasate astfel incat suma elementelor atacate sa fie cat mai mare.
Cerinta
Scrieti un program care sa determine suma elementelor atacate (maxima posibil).
Date de
intrare
Fisierul de intrare ture.in
va contine pe prima linie un numar natural N,
cu semnificažia din enunt. Pe fiecare dintre urmatoarele N
linii se afla cate N numere naturale,
reprezentand elementele matricei.
Date de iesire
Fisierul de iesire ture.out
va contine o singura linie pe care va fi scrisa suma maxima.
Restrictii
2 <= N <= 100
Elementele matricei sunt numere naturale <
255.
Exemplu
ture.in | ture.out | Explicatie |
5
4 2 2 3 3 4 2 1 4 0 1 3 4 0 1 4 3 0 2 3 0 0 3 0 4 |
40 |
Prima tura va fi plasata īn pozitia (4,3),
iar cea de a doua tura va fi plasata īn pozitia (2,5) |
Timp maxim de executie/test:
1 secunda