The original version of this problem was proposed by members of KEYENCE Corp.

Consider whether \(P\) or more projects can be made.

Let \(sum\) be the sum of \(\min(A_i,P)\) over \(i\,(1 \leq i \leq N)\). If \(P \times K > sum\), then obviously it is impossible to make \(P\) or more projects. In fact, we can prove that if \(P \times K \leq sum\), then we can make \(P\) or more projects.

Therefore, we can do binary search for the solution to solve the problem.

When determining \(P\times K > sum\), be careful of the overflow.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k; cin >> n >> k;
    vector<long long> v(n);
    for(long long &x : v) cin >> x;
    long long ok = 0, ng = 1e18 / k;
    while(ng - ok > 1){
        long long md = (ok + ng) / 2, sum = 0;
        for(long long x : v) sum += min(x, md);
        if(sum >= k * md) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}