Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

KHPA - Կարենի և Հարրի Փոթերի արկածները

Կարենը սիրում է ժամանակ առ ժամանակ համալսարանից հետո տուն գնալ ոտքով, և այսօր այդ օրերից մեկն է: Համալսարանը գտնվում է կոորդինատային ուղղի 0 կոորդինատով կետում, իսկ Կարենի տունը՝ L կոորդինատով կետում։ Կարենը չի գնում 0 կետից ձախ և իր տնից աջ, այսինքն քայլում է միայն [0, L] հատվածում: Նա սկսում է իր ճանապարհորոդությունը ամբողջ կոորդինատով կետից, կարող է շարժվել միայն աջ կամ ձախ և կարող է փոխել իր ուղղությունը միայն ամբողջ կոորդինատով կետերում։ 
Ինչպես բոլորս գիտենք՝ Հարրի Փոթերը հայտնի հրաշագործ է և փորձում է ամեն գնով հաղթել Վոլդեմորտին: [1, L]հատվածի ամբողջ կոորդինատով կետերում կան հորքրուքսներ, որոնք Հարրին ցանկանում է ձեռք բերել՝ Վոլդեմորտին հաղթելու համար: X կոորդինատով կետում կա ai հատ հորքրուքս, բայց կան նաև անպետք իրեր։ Հարրին ցանկանում է Կարենի օգնությամբ հավաքել որոշ հորքրուքսներ, իսկ մնացած հորքրուքսները հավաքել ինքնուրույն: Քանի որ Հարրին հրաշագործ է, նա կարող է Կարենին ուղարկել [0, L] հատվածի կամայական ամբողջ կոորդինատով կետ, իսկ հետո նաև ղեկավարել Կարենի շարժը: 
Երբ Կարենը անցնում է X – 0.5 (որտեղ X-ը ամբողջ թիվ է) կոորդինատով կետով, Կարենի մոտ ավելանում է Xկոորդինատով կետում գտնվող իր։ Եթե X կոորդինատով կետում դեռ կա հորքրուքս, ապա Կարենի մոտ հայտնվում է այդ հորքրուքսը։ Հակառակ դեպքում՝ անպետք իր: Ճանապարհորդության ավարտին Հարրին վերցնում է Կարենի հավաքած բոլոր իրերը։ 
Հարրին այժմ ցանկանում է իմանալ, թե նվազագույնը ինչքան էներգիա նա պետք է ծախսի, որպեսզի Կարենի մոտից իրարը վերցնելուց հետո նա ունենա բոլոր հորքրուքսնեը, և չունենա անպետք իրեր: 
Կարնեի մոտից իրերը վերցնելուց հետո Հարրին կարող է օգտագրծել հետևյալ 2 կախարդանքներից յուրաքանչյուրը ինչքան ցանկանա, սակայն ամեն անգամ որևէ կախարդանք օգտագործելը նրանից տանում է 1 էներգիա.

    1. Նա կարող է վերացնել անպետք իր,
    2. Նա կորող է իր մոտ բերել Կարենի չհավաքած հորքրուքսներից որևէ մեկը։
Հարրին՝ իմանալով, որ Դուք քաղաքի ամենալավ ծրագրավորողն եք, խնդրում է Ձեզ օգնել իրեն հասկանալ, թե նվազագույնը ինչքան էներգիա նա պետք է ծախսի, որպեսզի ունենա բոլոր հորքրուքսները և ոչ մի ավելորդ իր:

 

Մուտքային տվյալներ

Տրված են L-ը (1 ≤ L ≤ 2 · 105) և L հատ թիվ, որտեղ ai - ն (1 ≤ i ≤ L) i կոորդինատով կետում հորքրուքսների քանակն է (0 ≤ ai ≤ 109):

Ելքային տվյալներ

Պետք է արտածել, թե նվազագույնը ինչքան էներգիա պետք է ծախսի Հարրին՝ իր նպատակին հասնելու համար:

Օրինակներ

Մուտք.
4
1 0 2 3

Ելք.
1
Մուտք.
8
2 0 0 2 1 3 4 1

Ելք.
3

Ավելացրեց.Andreasyan
Ամսաթիվ.2019-03-18
Ժամանակի սահմանափակումը.0.100s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Մարզային 2019

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.