#jag2018summerday2d. [jag2018summer_day2_d]Knapsack And Queries
[jag2018summer_day2_d]Knapsack And Queries
Problem Statement
First, you are given a positive integer .
You have a knapsack, this is empty at first.
You have to perform queries.
-
In each query, you have first to perform either
ADD
orREMOVE
operation, and then performFIND
operation. -
ADD
operation : You are given positive integers . You put the cookie whose weight is and whose value is to the knapsack. -
REMOVE
operation : You take out the cookie with the smallest weight from the knapsack and eat it. -
FIND
operation : You are given non-negative integers . You answer the following question:- Can you choose cookies from the knapsack so that the sum of the weights of selected cookies satisfies
- If you can't, output
-1
. - Otherwise, output the maximum sum of the values of selected cookies.
Constraints
-
-
-
-
-
The cookie given by an
ADD
operation is strictly heavier than any cookie which was added by a previousADD
operation. -
When executing
REMOVE
operation, the knapsack isn't empty. -
Queries are Online Query. Queries are encrypted as described later.
Input
Input is given from Standard Input in the following format:
:
-
-
Queries are Online Query. You can get by decoding .
-
is query type.
- When , it involves
ADD
operation +FIND
operation. - When , it involves
REMOVE
operation +FIND
operation.
- When , it involves
-
When , you can assume that and .
Decryption
We prepare the decryption code with C++11 (or later), Java, D, C#.
Use class Crypto
for decryption, the code of class Crypto
is below.
C++
Java
D
C#
The procedure of decrypto:
- First, you make an instance of
class Crypto
. - In each query,
- call the
decode
function for each of in order. The return values are . - call the
query
function with the result of theFIND
operation.
- call the
The sample code of C++ is below.
The sample codes of Java, D, C# are below.
Java
D
C#
Remark:
- You don't need to find vulnerability of this encryption.
class Crypto
consume time at most about ms when .
Output
Print results of FIND
operation, one per line.
Sample Input 1
Sample Output 1
The result of decoding this input is as follows.
Knapsack
Selected Cookies
(w, v) = {(5, 10)}
{(5, 10)}
{}
{}
{(7, 10)}
-1
{(7, 10), (12, 11)}
{(7, 10), (12, 11)}
{(12, 11)}
-1
{(12, 11), (22, 10)}
{(12, 11)}
{(12, 11), (22, 10), (32, 100)}
{(12, 11), (32, 100)}
Sample Input 2
Sample Output 2
The result of decoding this input is as follows.