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

coinbag Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

coinbag.html



Josephine was trying to stuff all her coins to a bag. Unfortunately, because her coins were so big, she could not fit them into her bag. Even though she tried her best to squeeze a perfectly solid coin, she did not succeed.

Write a program to help her decide which coins to fit into her bag.

Given n (1 ≤ n ≤ 500) coins of w[i] weight and v[i] value (0 ≤ w[i], v[i] ≤ 500), what is the maximum value you can fit into a bag of size m (1 ≤ m ≤ 500)?

Points: 100

Input Format

Line 1: Two integers, n and m, representing the number of coins and the size of the bag.

Line 2...n: Two integers on each line, with the (i + 1)th line containing the weight w[i] and value v[i] of coin i.

Sample Input

3 5
5 2
2 1
3 2

Output Format

Line 1: A single integer which is the maximum value that can be fitted into the bag of size m.

Output

3

Output Details

The maximum value can be achieved with the two coins with weight 2 and value 1, and the coin with weight 3 and value 2.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

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