Language: C++


#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

    LL N, M, V, P;
    cin >> N >> M >> V >> P;
    vector<LL> A(N);
    rep(i, N) cin >> A[i];
    sort(A.begin(), A.end());

    //! Binary search. (l, r]
    LL l = -1;
    LL r = N-1;

    while (1 < r-l) {
        LL m = (r+l) / 2;

        if (N-m <= P) {
            //! m is already in top P before adding points
            r = m;
            // cout << "N-m <= P, setting m to r" << endl;
        } else {
            // cout << "P < N-m" << endl;
            LL maxM = A[m]+M; //! the max points that m can take
            //! the best case for m is to distribute all points to low score problems in greedy way
            LL remaining = max(0, V-m-1) * M;

            //! distribute points to top (P-1) problems
            remaining -= (P-1) * M;
            remaining = max(0, remaining);

            // cout << "maxM, remaining = " << maxM << ' ' << remaining << endl;

            bool ok = true;
            for (LL i = N-P; ok && m < i; --i) {
                if (maxM < A[i]) {
                    ok = false;
                } else {
                    remaining -= min(M, maxM-A[i]);
                    remaining = max(0, remaining);
                }
            }
            if (0 < remaining) {
                // cout << "ok = false, because 0 < remaining" << endl; 
                ok = false;
            }
            
            if (ok) {
                r = m;
            } else {
                l = m;
            }
        }
        // cout << "BOTTOM l , r = " << l << ' ' << r << endl;
    }

    cout << (N-r) << endl;

    return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:51:31: error: no matching function for call to 'max(int, LL)'
   51 |             LL remaining = max(0, V-m-1) * M;
      |                            ~~~^~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:51:31: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'LL' {aka 'long long int'})
   51 |             LL remaining = max(0, V-m-1) * M;
      |                            ~~~^~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:5:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:51:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   51 |             LL remaining = max(0, V-m-1) * M;
      |                            ~~~^~~~~~~~~~
a.cc:55:28: error: no matching function for call to 'max(int, LL&)'
   55 |             remaining = max(0, remaining);
      |                         ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:55:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'LL' {aka 'long long int'})
   55 |             remaining = max(0, remaining);
      |                         ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:55:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   55 |             remaining = max(0, remaining);
      |                         ~~~^~~~~~~~~~~~~~
a.cc:65:36: error: no matching function for call to 'max(int, LL&)'
   65 |                     remaining = max(0, remaining);
      |                                 ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:65:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'LL' {aka 'long long int'})
   65 |                     remaining = max(0, remaining);
      |                                 ~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:65:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   65 |                     remaining = max(0, remaining);
      |                                 ~~~^~~~~~~~~~~~~~