TLE '16 Contest 6 (Mock CCC) J2 - Carol's Flowers

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Mr. C has had a change of heart from being a lonely developer to finally getting a girlfriend, Ms. C (they are not related by blood). As the courteous fellow he is, he has decided to buy some flowers for her.

Ms. C wants N flowers with flower i costing c_i, a positive integer. The store, Carol's Flowers, has F flowers, where F \ge N. Each flower can only be bought once, and since Mr. C lives in a computer science problem, the cost of the flowers are exponential. In other words, the second flower he buys is the price of the flower squared, and the third flower he buys is the price of the flower cubed, and so on.

Mr. C is poor, but he needs to satisfy Ms. C. Can you find out the minimum value Mr. C has to pay for N flowers?

Input Specification

The first line of input contains 2 integers, F and N (1 \le N \le F \le 1000).

The next F lines contain 1 integer each. The i^{th} line contains the positive integer c_i (1 \le c_i \le 1000).

  • For 5 of the 15 available marks, N \le 10 and c_i \le 10.
  • For an additional 5 of the 15 available marks, N \le 100 and c_i \le 100.

Output Specification

A single integer representing the minimum price Mr. C has to pay for N flowers mod 1\,000\,000\,007 (= 10^9+7).

Sample Input

7 3

Sample Output


Explanation for Sample Output

The cheapest way to buy 3 flowers is to buy the last flower, the third flower, and the first flower. That is, 3^1+2^2+2^3=15 is the minimum price.


  • -3
    rogerthatawesome  commented on Jan. 19, 2018, 8:49 p.m.

    I got only the first case right

  • 0
    JerryLin  commented on Feb. 20, 2017, 9:16 p.m.

    Where would we input i?

    • 0
      loltrollkill  commented on Jan. 19, 2018, 6:04 p.m.

      sad to find that nobody replied to your comment in 1 whole year.

  • 0
    serawang  commented on Feb. 20, 2017, 12:10 p.m.

    if the price of the sum of the flowers are more expensive than the sum in c's wallet, should I mod the sum(of the flowers)?

    • 0
      ZQFMGB12  commented on Feb. 20, 2017, 12:15 p.m.

      The wallet has nothing to do with this problem. It has been removed from the problem description to prevent confusion.

      Sorry for any inconvenience this may have caused.