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

tourist Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

tourist.html

Problem Description

An eccentric tourist has decided to visit some of the most beautiful Italian cities. In his luggage, together with an Italian/wherever-he-comes-from phrasebook, he has a number of large coins made with pure gold.

The tourist has already chosen a list of N cities to travel across, and intends to follow his plan until he runs out of money (so he might not reach the last cities in his list). He starts in the first city, and travels from one city to the next one, following the order he has established and paying one golden coin per route.

When he is in a city (included the first one), he can spend the night in a hotel in order to visit that city. However, he can only stay one night in each city at maximum. If he does so, he has to pay the hotel one golden coin, and his happiness increases by a value that depends on a city.

Clearly, the tourist is interested in maximising the happiness he gains by suitably using the coins during this holiday. Given an array containing each of the amount of happiness that can be gained by visiting each city, calculate the maximum amount of happiness he can gain with K golden coins.

- Adapted from IOI Practice Task 2012, tourist.

Input

The first line of input will contain two integers, N and K.
The second line of input will contain N integers, with the ith integer representing the amount of happiness gained if the tourist visits city i.

Output

Your output should contain one integer, the maximum amount of happiness that can be gained using K golden coins.

Limits

For all testcases, K and happiness value will range from 0 to 231-1.
Subtask 1 (18%): N ≤ 10.
Subtask 2 (1%): N = 42.
Subtask 3 (22%): N ≤ 200.
Subtask 4 (26%): N ≤ 1 000.
Subtask 5 (33%): N ≤ 1 000 000.
Subtask 6 (0%): As per sample testcases.

Sample Input 1

4 5
4 5 2 7

Sample Output 1

12

Tags

IOI 2012 Practice Tasks, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
118201s256MBMinimum
21201s256MBMinimum
322601s256MBMinimum
426801s256MBMinimum
5331001s256MBMinimum
6011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o tourist -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.