Depot
TCO19 SRM 742 · 2018-11-27 · by misof
Problem Statement
This problem has a non-standard time limit: 8 seconds.
We work in a depot in which various packages are stored.
Currently, the depot is empty.
We know a precise schedule in which the packages will arrive to the depot.
The schedule is given in the
We are expecting exactly one transport ship. The transport ship will arrive at the end of some day and it will have some capacity, but we do not know either. In order to be prepared for various alternatives, we need you to write a program that will answer many queries.
Formally, let Q(D,S) be the following query: "Suppose that the ship arrives at the end of day D and that it can carry packages with total size S. Will we be able to fill the ship perfectly?" In other words, Q(D,S) is true if and only if there is a subset of packages that have been delivered during days 1 through D (inclusive) such that the sum of their sizes is exactly S.
The queries you should answer are given in the
Return the total number of queries with a positive answer. (If you were asked multiple queries with the same parameters, you should still count each of them as a separate query.)
Constraints
- arrivals will contain between 1 and 20 elements, inclusive.
- Each element in arrivals will be of form "D I M S", where D, I, M, and S are integers.
- queries will contain between 1 and 20 elements, inclusive.
- Each element in queries will be of form "D S" or "D S A1 B1 A2 B2 N", where D, S, A1, B1, A2, B2, and N are integers.
- The integers D, I, M, A1, and B1 in arrivals and queries will be between 1 and 10^9, inclusive.
- The integers S, A2, B2, and N in arrivals and queries will be between 1 and 300,000, inclusive.
- All integers will be specified without leading zeros.
- Consecutive integers in a string will always be separated by a single space. There will be no other spaces anywhere.
{"3 2 4 2", "4 3 2 3"}
{"3 1", "3 2", "3 4", "4 2", "5 3", "5 5", "7 6", "9 1"}
Returns: 5
The image shows arrivals of four packages of size 2 (denoted by letters A) and two packages of size 3 (denoted by letters B): B A B A A A ---------------------------------------------> 1 2 3 4 5 6 7 8 9 days On day 3 we have only one package of size 2, thus answers to queries "3 1", "3 2", and "3 4" are negative, positive, and negative, respectively. On day 4 we could use package of size 2 which have arrived day before, so query "4 2" is positive. On day 5 we could use single package of size 3 or combine packages of size 2 and 3, thus both queries "5 3" and "5 5" are positive. On day 7 we could use a set of three packages of size 2 or two packages of size 3 to get total sum of 6, thus "7 6" is also positive. We don't have packages of size 1, thus "9 1" is negative.
{"3 2 4 2", "4 3 2 3"}
{"3 4 2 10 1 6 4", "5 3 8 9 8 9 3", "3 2"}
Returns: 5
This is exactly the same set of queries as in test #0. The first compressed entry specifies queries "3 4", "5 5", "7 6", and "9 1". The second compressed entry specifies "5 3", "4 2", and "3 1".
{"1 1 1 3"}
{"1 1 1 5 1 5 100"}
Returns: 20
We have exactly one package of size 3 (obtained on day 1). There are queries "1 1", "2 2", "3 3", "4 4", and "5 5" repeated 20 times.
{"1 1 20000 1"}
{"1 10000 2 20000 10000 10000 10000", "2 10000 2 20000 10000 10000 10000"}
Returns: 10001
{"1 1 1 1"}
{"1 1"}
Returns: 1
{"1 147 1 1"}
{"107 107 107 2 107 2 10"}
Returns: 5
A single package of size 1 arrives on day 1. There are five queries of the form "1 1" (which have a positive answer) and five queries of the form "2 2" (negative). Note that when a query is compressed the values D, S, and Aj may be bigger than the corresponding Bj. Make sure you compute the Di and Si correctly.
Submissions are judged against all 57 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Depot with a public method int countPositive(vector<string> arrivals, vector<string> queries) · 57 test cases · 2 s / 256 MB per case