Cześć! Mam do rozwiązania takie zadanie, że na wejściu mamy daną pewną liczbę 'n' (1 <= n <= 1000), a następnie kwadratową tabelkę n*n (przy czym każdy element jest z przedziału 1...10^6). Teraz mamy usunąć jeden wierz i jedną kolumnę tak, aby suma wszystkich elementów tabelki była jak najmniejsza i wypisać tą sumę. Dla dokładniejszego zrozumienia, przedstawiam tutaj test przykładowy:
Wejście:
4
2 0 1 2
5 7 0 3
1 1 9 1
0 1 0 2
Wyjście:
10
(ponieważ możemy usunąć drugi wiersz i trzecią kolumnę)
Moim pierwszym pomysłem było aby od sumy wszystkich elementów odjąć kolumnę o największej sumie oraz wiersz o największej sumie i dodać do tego element, który leży na przecięciu tej kolumny i wiersza (dodać, ponieważ element na przecięciu nie może być liczony dwa razy). Niestety działa tylko dla 1/3 wszystkich testów.