Առավելագույն ընկնող ուղու գումարը
Տրված է
h բարձրությամբ և w լայնությամբ ցանց։ Ձեզ խնդրում են հաշվել այն առավելագույն գումարը, որը հնարավոր է ստանալ, շարժվելով ցանցի վերևի տողից դեպի ներքևի տող: Յուրաքանչյուր քայլով թույլատրվում է շարժվել մի տող ներքև, գնալով (r + 1, c - 1), (r + 1, c) կամ (r + 1, c + 1) վանդակներից մեկի ուղղությամբ: Այդ պատճառով էլ ստացվող ճանապարհը անվանում ենք «ընկնող», որովհետև կարելի է ասել, որ «ընկնում ենք» ցանցի ամենավերևի տողից մինչև ամենաներքև: Գտեք այդ ուղու առավելագույն գումարը:ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
h և w (1 ≤ h, w ≤ 100):Հաջորդ
h տողերից յուրաքանչյուրն ունի w թիվ (-100 ≤ ≤ 100), որոնք ներկայացնում են ցանցի r-րդ տողի և c-րդ սյան արժեքները:Ելք
Ծրագիրը պետք է տպի ընկնող բոլոր հնարավոր ուղիներից ստացվող առավելագույն գումարը:
Օրինակներ
Մուտք | Ելք |
3 3
2 1 3
6 5 4
7 8 9 | 17 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB