Few months ago I could solve 4 problems consistently and sometimes 5th problem too and today I could solve only 2 out of 8 problems. I am evolving, just backwards :(

I tried using a priority_queue.

First put the K biggest departments onto the queue, then iterate the remaining departments biggest first.

Take the smallest department from the q, add the current department, and push it back onto the queue. Then, in the end, the smallest department on the queue should be ans. But WA for some reason:/

Let's say you are able to do $$$X$$$ projects, then consider iterating over $$$A_i$$$ in non-increasing fashion. Let's also have a variable $$$take$$$ initialized to $$$0$$$, which stores the amount of members assigned to each of the $$$X$$$ projects.

If for some $$$i$$$, $$$A_i$$$ $$$\geq$$$ $$$X$$$, then we can simply pick $$$X$$$ members of this department and individually assign them one of the $$$X$$$ projects. In this case increment $$$take$$$ by $$$1$$$.

If $$$A_i$$$ $$$\leq$$$ $$$X$$$, then let's store the sum of such $$$A_i$$$ in another variable $$$res$$$. Finally increment $$$take$$$ by $$$res / X$$$.

If $$$take$$$ $$$\geq$$$ $$$K$$$, we can do $$$X$$$ or more projects. So you can binary search over $$$X$$$.

Problem D is exactly similar to the problem in this blog

When you set X projects, you can not assign over X persons from one department. it is proved by pigeonhole principle.

If I was a beginner I would've given up all hope and left CP after this round

I can't agree with you more

We can use __int128 integer type in atcoder.

I dont see where do you need to you bigint for binary search

l = 0, r = 1e18 ==> mid = 5e17 mid * k ==> 5e17 * 200000 will overflow

You are doing

if (sum >= mid * k)

if l is 0 and r is 1e18

mid is 5e17

and mid * k will be greater than long long range

you can just use something like

if ((__int128)sum >= (__int128)mid * k)

It is enough to check the max H*W different values of a[i][j].

me too

Edit : I think I have understood in a visual way

For example

4 projects(k=5):

1 : 1 2 3 5 6

2 : 1 2 3 4 5

3 : 1 2 3 4 5

4 : 1 2 3 4 5

Watch one thing as number of element 5 is less than p it won't ever collide with 4, that's the thing

They have used induction to prove that when $$$P*K \leq sum$$$ where $$$sum = \sum_{i=0}^n min(A_i, P)$$$, we can always construct at-least $$$P$$$ projects

We sort the array $$$A$$$ in non-increasing order (let's call this array $$$B$$$) and use the following construction: Pick the first $$$K$$$ elements from $$$B$$$, take 1 employee from each and create a new project

Here is the proof by induction:

1. Let's say we have more than $$$K$$$ departments in $$$B$$$ such that $$$B_i \geq P$$$. Here we can simply create $$$P$$$ projects from the first $$$K$$$ elements of $$$B$$$

2. If above condition doesn't hold, we can still pick first $$$K$$$ departments from $$$B$$$, choose $$$1$$$ employee from each and create $$$1$$$ project. Now, we are left with $$$P-1$$$ more projects to construct. But the $$$sum$$$ has also changed, let's say it becomes $$$sum'$$$. The following equation holds true : $$$sum \geq sum' \geq sum-K$$$. This is because we choose $$$min(A_i, P)$$$ employees for each $$$i$$$ while calculating $$$sum'$$$. So, we may end up subtracting $$$1$$$ or we may end up subtracting nothing for each $$$i$$$ in $$$[1, K]$$$ depending upon whether $$$A_i \geq P$$$ or not.

Now, we end up with following simple derivation that proves that by induction, we can construct remaining $$$P-1$$$ projects in a similar way.

Hope this helps!