시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Mirko je na sajmu kupio novi pametni Roomba usisivač. Kako bi ga isprobao, napravio je kutiju od kartona i njeno dno podijelio na (N + 1) redaka i stupaca označenih brojevima od 0 do N. Na svako polje u kutiji Mirko je postavio određeni broj novčića. U kutove, odnosno na polja (0, 0), (0, N), (N, 0) i (N, N) stavio je zlatne novčiće, a u preostala polja srebrne. Usisivač se na početku nalazi na polju (0, 0) te se u jednoj sekundi može pomaknuti na jedno od (najviše) osam susjednih polja.
Mirko je zapovjedio svome pametnom usisivaču da pokupi sve zlatne novčiće i što više srebrnih novčića te da se za točno 4·N sekundi vrati na polje s kojeg je i krenuo. Međutim, usisivač je samo tužno odgovorio da ne zna izračunati putanju kojom će pokupiti najviše novčića.
Napišite program koji će izračunati najveći broj novčića koje usisivač može pokupiti.
U prvome retku nalazi se prirodan broj N (1 ≤ N ≤ 500).
U sljedećih N + 1 redaka nalazi se po N + 1 prirodnih brojeva, koji predstavljaju broj novčića na pojedinom polju kutije. Broj novčića u svakom polju bit će manji ili jednak 10000.
U prvi i jedini redak treba ispisati najveći broj novčića koje usisivač može skupiti u 4·N sekundi tako da se na kraju vrati na početnu poziciju i pokupi sve zlatne novčiće.
2 1 1 1 1 10 1 1 1 1
17
3 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7
51