oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

cookieclicker Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

cookieclicker.html

Problem Description

Remember the Cookie Clicker Craze last year? Now that it is pretty much over (or is it?), Peanut is playing Cookie Clicker alone at home. With no one else competing for the number of cookies baked, Peanut creates his own variant of the Cookie Clicker game. In this new variant of Cookie Clicker, there are P different powerups that Peanut can buy, each costing 1 cookie. Each of these powerups also add a certain amount of CpS to Peanut's game. However, there is a catch. Every time a powerup gets bought and used, the number of CpS gained from this powerup decreases by 10%, rounded down to the nearest integer.

For example, if a certain powerup that gives you 6 CpS is bought, the next time you buy and use this powerup, you will only gain 6 x 0.9 = 5.4 = 5 (rounded down) CpS. The next time you use this powerup, you will gain 5 x 0.9 = 4.5 = 4 CpS, and so on. Given the number of cookies Peanut has to spend, N, the number of powerups Peanut can use, P, and the starting CpS gain for each powerup, find out the maximum CpS Peanut can achieve with N cookies to spend.

Input

The first line of input will contain two integers, N and P.
The second line of input will contain P integers, with the ith integer representing the starting CpS of the ith powerup.

Output

Your output should contain one integer, the maximum CpS Peanut can gain.

Limits

The starting CpS gained from each powerup will always be less than 231-1.
Subtask 1 (19%): 1 ≤ N, P ≤ 100.
Subtask 2 (24%): 1 ≤ N, P ≤ 1000.
Subtask 3 (28%): 1 ≤ N, P ≤ 100000.
Subtask 4 (29%): 1 ≤ N ≤ 231-1. 1 ≤ P ≤ 100000.
Subtask 5 (0%): As per sample testcases.

Sample Input 1

7 4
1 2 3 4

Sample Output 1

17

Sample Input 2

4 3
1 1 1

Sample Output 2

3

Tags

Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
119201s32MBMinimum
224401s32MBMinimum
328601s32MBMinimum
429803s32MBMinimum
5021s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o cookieclicker -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.