Problemi 21

Kërkesa

Një byrektore do zhvendoset nga qyteti A në qytetin B në një nga N ditët e ardhshme (të numëruara nga 1 deri në N). Ajo mund të zhvendoset brenda natës, ose para ditës 1, ose pas ditës N, ose në ndonjë nga netët midis tyre. I zoti do që ta zgjedhë natën e zhvendosjes në mënyrë të tillë që fitimi të jetë sa më i madh. Duke ditur fitimin që mund të nxirret në secilën nga ditët, në secilin qytet, sa është fitimi më i madh që mund të nxjerrë byrektorja në këto N ditë?

Referenca: https://www.codechef.com/LTIME71B/problems/FASTFOOD

Shembull

$ cat input.txt
3
3
2 3 2
10 3 4
4
7 5 3 4
2 3 1 3
2
10 1
1 10

$ python3 prog.py < input.txt
17
19
20

Jepet numri i ditëve N, dhe në dy rreshtat pasardhës jepen fitimet për secilën nga këto ditë në qytetet A dhe B.

Në rastin e parë fitimi më i madh merret nqs lëvizja bëhet para ditës së parë.

Në rastin e dytë fitimi më i madh merret nqs lëvizja bëhet pas ditës së fundit.

Në rastin e tretë fitimi më i madh merret nqs lëvizja bëhet pas ditës së parë.