It is sponsored by KEYENCE. If you search all past KEYENCE sponsored contests on atcoder, all of them have their competition pages red.

Happy National Day!

Because it is sponsored by Keyence, just like ABC 325 ( the page is also red. ).

Happy National Day!

***_fan has been -37! Share it!

SFLSdalao%%%

Happy National Day!

Let's find the minimal cost for $$$i$$$-th process to produce $$$y$$$ products. Assume we bought $$$i$$$ machines of first type and $$$j$$$ machines of second type.

$$$a \cdot i + b \cdot j \ge y$$$

$$$p \cdot i + q \cdot j \rightarrow min$$$

Let the first type of machine be "better" than the second: $$$\frac{a}{p} \ge \frac{b}{q}$$$. If we could buy fraction of machine, then we would use only the first type. But it can be the case, that we it is more effective to buy the second type machine (for example, if it is not effective, but we need only one last product, while the first type machine produces a lot).

There is one quite known fact: $$$j$$$ is limited by some number. If we have $$$b \cdot (\alpha + \beta)$$$, where $$$j = \alpha + \beta$$$ and $$$b \cdot \alpha$$$ is divisible by $$$a$$$, then we can increase $$$i$$$ by $$$\frac{b \cdot \alpha}{a}$$$ and decrease $$$j$$$ by $$$\alpha$$$. This means, that $$$j$$$ is not greater, than $$$max(a, b)$$$ (in these case, it is possible to choose such $$$\alpha$$$, which is equal to $$$a$$$, so $$$b \cdot \alpha$$$ will be divisible by $$$a$$$).

So we just check all possible $$$j$$$ from $$$0$$$ to $$$max(a, b)$$$.

For the whole problem. Use binary search on answer and in check function calculate sum if all these $$$p \cdot i + q \cdot j \rightarrow min$$$ and check if it is not greater than $$$x$$$.

2 ways to do that, both ways involve trying out all possibilities (Notice that N is small here)

• Backtracking to try both groups for every department.
• Enumerating all bitmasks which represent which departments will be in group 1 (The bit is off) or group 2 (The bit is on) (For example, if N is 5, a bitmask of 01010 means the first, third and fifth departments will be in group 1, the second and fourth departments will be in group 2).

Well I thought it will be at most 15000 but it's hard to believe that it's at most 100.

For some machine X, Y, say that X produces A products and Y produces B products. Note that any A machines of type Y can be replaced by B machines of type X, and the amount produced stays the same.

Now, suppose that Y is more efficient than X. Then, observe that it is never optimal to choose more than B machines of type X, as they can always be exchanged for Y, resulting in the same production but less cost.

A and B are bounded by 100, hence why jiangly can do this.

Hope this helps!

can you tell why the range was only from 0 to 15000

Please remove extra cout << ' ' statements.

53 cases are a lot!

do binary search on the answer. now notice that, for each process, one of the machines is better than the other: supose we want to make lcm(Ai, Bi) products using a single machine. then, it will cost Pi * lcm(Ai,Bi)/Ai using the first machine and Qi * lcm(Ai, Bi)/Ai using the second machine. without loss of generality, supose the first machine will require less money to make this amount of products. then, you will never make >= lcm(Ai, Bi)/Bi products using the second machine (you could simply make them using the first machine with a lower cost). then, you can just brute force the amount of times you will use the second (worst) machine, which will be <= lcm(Ai, Bi)/Bi <= Ai products.

Same, but I took advantage of small N and did ternary search to reduce the search space to <1e4 lol

This is the same as jiangly's idea, Can you prove why it's beneficial to use ratio $$$a_i / p_i$$$ and $$$b_i / q_i$$$?

For every process i, it is always beneficial to greedily buy the machine with the better output / cost ratio.

So buy that machine as much as possible, and the remainder products needed will be < 100. Now buy the other machine to fill this remainder.

Both the statements are incorrect. You just got lucky with your code, because you haven't implemented what you are thinking. Your code is correct though.

Greedily buying efficient machines as much as possible is not optimal. In fact, as counter intuitive as it may seem, you need to buy inefficient machines first (explore all possibility instead of buying greedily) and only then should you buy efficient machines.

I talk about a counter example to your idea in my video

what it requires to reach yellow? solving all the problems fast?

congratulations! :D

Try all subsequences using a complete search with bitmasking or recursion.

W=min(W1, W2, W3) =>

W=min(4, 1+3, 4) = 4.