Državna razina / Primjena algoritama OŠ 2023. / Osnovna škola (7. razred) - 3. zadatak

Neka je zadana tablica od N redaka i M stupaca i neka se u svakom polju tablice nalazi neki cijeli broj. To su oni brojevi koji mogu biti pozitivni, nula i negativni. Pred tebe postavljamo sljedeći izazov:

• odaberi i stani na jedno polje u tablici te uzmi broj koji tamo piše;
• nastavi se kretati po tablici i skupljaj brojeve. Ništa posebno, kažeš? Evo još uvjeta:
• tijekom svog kretanja smiješ napraviti najviše K skretanja (K će biti 0, 1 ili 2);
• nikad ne smiješ izaći iz tablice;
• nikad ne smiješ ponovno doći na polje na kojem se već bilo. Znači, cilj ovakvog kretanja po tablici je sakupljati brojeve po poljima pod zadanim uvjetima i na kraju imati što je moguće veći zbroj skupljenih brojeva. Ako su svi brojevi u tablici negativni dozvoljeno ti je odustati od kretanja i imati zbroj sakupljenih brojeva jednak nula. Dodatna vizualna pojašnjenja kretanja:
• primjer kretanja po tablici s nula skretanja:
• primjer kretanja po tablici s jednim skretanjem:
• primjer kretanja po tablici s dva skretanja:

Ulazni podaci

U prvom su retku prirodni brojevi N i M (2 ≤ N, M ≤ 1000), brojevi iz teksta zadatka. U sljedećih N redaka je po M cijelih brojeva Aij (-1000 ≤ Aij ≤ 1000), brojevi iz tablice iz teksta zadatka. U posljednjem retku je cijeli broj K (0 ≤ K ≤ 2), broj iz teksta zadatka.

Izlazni podaci

U prvi redak ispiši najveći mogući prikupljeni zbroj bodova iz teksta zadatka.

Bodovanje

U primjerima ukupno vrijednima 20 bodova vrijedit će K = 0. U primjerima ukupno vrijednima 30 bodova vrijedit će K = 1. U primjerima ukupno vrijednima 40 bodova vrijedit će K = 2. Također, u primjerima ukupno vrijednima 30 bodova vrijedit će Aij ≥ 0. Isto tako, u primjerima ukupno vrijednima 20 bodova vrijedit će N, M ≤ 10, a u primjerima ukupno vrijednima dodatnih 25 bodova vrijedit će N, M ≤ 100.

Primjer zadatka

Ulaz

4 4
5 3 4 1
3 5 0 3
5 5 5 2
2 1 5 5
0

Izlaz

17

Ulaz

5 5
-2 3 1 -2 3
3 5 -5 5 -2
3 5 -3 -1 3
3 -5 -4 5 -4
5 5 4 5 -5
1

Izlaz

28

Ulaz

3 4
1 -5 1 0
-5 4 -1 -3
3 5 1 1
2

Izlaz

12

Opis prvog probnog primjera:

Opis drugog probnog primjera:

Opis trećegin probnog primjera: