I trust u.

good luck!!!

NO

This round will be rated for the participants with rating lower than 2100

And I've been banned for crawling...

What's crawling?

I hope you reach Cyan in this contest

i hope too

I hope you reach it :)

why unrated? trust yourself

click to see all of the contest registrants, and there is a button for changing to unrated

click to see all of the contest registrants, and there is a button for changing to unrated

agree with you. To me, E1 is much easier than D.

Can u give me some hints for E1? I don't know I made some observations but feel stuck now.

Looks like I found you again mate while scrolling, keep trying man you will make it to green. Also try to solve problems in an organized matter like do usaco they have cf problems and ones from other sites organized in every category. Like for example c was just dp nothing else as simple as that you just have to do some for a long time in the usaco

Just iterate on all $$$x \leq 3e5$$$.

you could consider every element in array, and check how many of its multiple exists in arrray. worse case array is [1,2,...,2e5] so 1st element takes N iterations 2nd element takes N/2 iterations so on, its just O(NlogN) now just check which x is optimal.

example: 50 150 450 x = 3 is optimal since 50*3 exists, and 150*3 exists, so you could get 2 items for free just maintain some freq array where fr[i] tells how many if x = i, how many items you get free

you need to check for all x [2 , max(ai)] , just think how you can optimize division get the sum quickly.

and answer for division will be same for a range of elements

Hi there, this is my solution for D. So you will try all X, if you have X, there 200000/X value that you can potentially keep. Now let say one of these value you can keep as J.If you divide all C[i] by X.All C[i] that has value from (J-1)*X+1 to J*X will become J.And the number of sign you can save is MIN(C[J],Number of sign from (J-1)*X+1 to J*X. Now that we have a solution, how do we know this can run in allowed time constraint. Let's say our complexity is 2e5/1 + 2e5/2 +...+2e5/2e5. This sum shall be equal to 2e5LOG. Hope this help.

Because Scanner is slow.

There is always a solution, so the minimum answer is 2. First, create a valid solution for both arrays, then see if you can swap any position. If you can, just multiply by 2 each time. 338832246

dp[0][1] would be 1, no?

dp[0][1] = 0; is wrong i guess it should also be initialized to 1

You are doing modular arithmetic wrong first and third additions are wrong while second and forth are correct

You set dp[0][1] to 0, it should be 1, cus if u only have the first elements, u can swap them.

NOOOOOOOOOOOOOOOOOOO (it's so over I can't even write the compilation command right)

I think changing the position of -o will fix the problem: g++ E.cpp -o E

Consider some final price, p. Now for some i, p = ceil(c[i] / x). Now, it's easy to see that we will get the same price p for not only c[i] costs but for a range of costs. Suppose x = 5, then ceil(50 / 5) = ceil(49 / 5) = ceil(48 / 5) = ceil(47 / 5) = ceil(46 / 5) = 10. So, a good idea is : we can find the range and work on how many times the elements in that range will appear in the original array.

p — 1 < c[i] / x <= p -> c[i] ∈ [(p — 1) * x, p * x]; x ∈ [2, max_cost]

We can simply store the frequency of each cost in a frq array and make another prefix sum array called pref such that pref[j] — pref[i — 1] = Number of occurrences of elements from the range i to j. Then iterate over all x and get the new sum of the array of costs. For each value of x, we'll get a result = sum — y * (n — cnt); where cnt = Number of elements in the range [x * (p — 1) + 1, p * x], p is calculated for the corresponding x. Finally maximize the ans. ans = max(ans, result); Time Complexity = O(max * log(max));