Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գինու արտադրություն

Դուք պատասխանատու եք գինու արտադրության գործարանի լոգիստիկ բաժնի համար։ Կա n տակառ, և ամեն օր դրանցից միայն մեկն է լցվում գինով։ Դուք յուրաքանչյուր տակառի համար գիտեք, թե քանի օր այն պետք է փակ մնա, նախքան բացելը։ Ձեր նպատակն է նվազագույնի հասցնել այն ընդհանուր ժամանակը, որի ավարտին հնարավոր կլինի բացել բոլոր տակառները։

Մուտք

Մուտքի առաջին տողում տրված է n բնական թիվը (1 ≤ n ≤ )։

Հաջորդ տողում տրված են n բնական թվեր (բաժանված բացատներով) (1 ≤ ≤ ), որոնք ցույց են տալիս, թե քանի օր պետք է ամեն տակառ փակ մնա, մինչ բացելը։

Ելք

Ծրագիրը պետք է տպի ամենափոքր հնարավոր ժամանակը, որի ընթացքում հնարավոր կլինի բացել բոլոր տակառները։

Օրինակներ

Մուտք

Ելք

4
2 3 4 3

6

6
39 19 38 39 22 35

41

Բացատրություն

  • Օրինակ 1 (թվերը ցույց են տալիս օրերի համարները).

    1. Լցնել այն տակառը, որը պետք է 4 օր փակ մնա

    2. Լցնել այն տակառը, որը պետք է 3 օր փակ մնա

    3. Լցնել այն տակառը, որը պետք է 3 օր փակ մնա

    4. Լցնել այն տակառը, որը պետք է 2 օր փակ մնա

    5. Բացել առաջին երկու օրերի ընթացքում պահեստավորված տակառները

    6. Բացել երրորդ և չորրորդ օրերի ընթացքում պահեստավորված տակառները ⇒ բոլոր տակառները կբացվեն

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue