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

salmon Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

salmon.html

Problem Description

Salmons are common in Japanese Restaurants. They can be served in a variety of ways: sashimi, sushi, steamed, salad.. etc

Rar the Cat is currently sitting in a Japanese Restaurant writing this problem statement. He has noticed that there is salmon in almost every single dish on the menu. However, upon scrutinization, he has found that this is because some dishes contain some other dishes. For example, a Premium Bento (Japanese Rice Set) contains Salmon Maki (Salmon Sushi).

The Premium Bento is priced at a higher price than the salmon maki and making it requires six salmon maki and five slices of salmon sashimi. On the other hand, one salmon maki requires two slices of salmon sashimi to make.

In view of the upcoming Chinese New Year, the Japanese Restaurant has also launched a Yu Sheng (Teochew Raw Fish Salad) dish that requires one hundred and seventy nine slices of salmon sashimi to create. One of this dish (Yu Sheng) is also included in a Chinese New Year Gift Box together with twenty four Japanese Bentos, sixty seven Salmon Maki and eighty eight slices of Salmon sashimi.

Rar the Cat is tempted to buy the salmon dishes but he has no money to buy from the Japanese Restaurants. Since Japanese Restaurants usually sell dishes for an expensive price, he decides to turn to a cheaper alternative -- NTUC FairPrice (Supermarket).

NTUC FairPrice sells salmon fishes as an entire fish. Being an experienced salmon fish eater, he estimates the salmon fish he plans to buy to be able to make exactly N slices of salmon sashimi. With this, he wants to know what is the maximum value of his salmon fish if he were to make the above salmon dishes (in $). To do so, he has provided you with a simplified menu of the Japanese Store.

Item Price per Item ($)
Salmon Sashimi 2
Premium Bento 60
Salmon Maki 7
Yu Sheng 588
Chinese New Year Gift Box 2888

Since Rar the Cat has limited amounts of other resources (Eg. Rice), he can only make up to 1023 of each item on the list.

Input

The input contains only a single integer, N.

Output

Output a single integer, the maximum value of his salmon fish if he were to make the above salmon dishes (in $). To do so, he has provided you with a simplified menu of the Japanese Store.

Subtasks

Subtask 1 (7 marks): 0 ≤ N < 17

Subtask 2 (46 marks): 0 ≤ N ≤ 2000

Subtask 3 (47 marks): 0 ≤ N ≤ 1000000

Subtask 4 (0 marks): Sample Testcases

Limit has been increased to N = 1000000

Sample Input 1

16

Sample Output 1

56

Rar the Cat can obtain the maximum value by making 8 Salmon Makis which are valued at $7 each.

Sample Input 2

1023

Sample Output 2

3643

Sample Input 3

32767

Sample Output 2

116956

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
17170.5s16MBMinimum
2461170.5s16MBMinimum
3472000.5s16MBMinimum
4030.5s16MBMinimum

Judge Compile Command

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