Submission #65509240

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<ll> A(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        vector<ll> A_desc = A, A_asc = A;
        sort(A_desc.begin(), A_desc.end(), greater<ll>());
        sort(A_asc.begin(),  A_asc.end());
        vector<ll> SH(N+1,0), SL(N+1,0);
        for(int i = 0; i < N; i++){
            SH[i+1] = SH[i] + A_desc[i];
            SL[i+1] = SL[i] + A_asc[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<ll> A(N);
        for(int i = 0; i < N; i++) cin >> A[i];
        vector<ll> A_desc = A, A_asc = A;
        sort(A_desc.begin(), A_desc.end(), greater<ll>());
        sort(A_asc.begin(),  A_asc.end());
        vector<ll> SH(N+1,0), SL(N+1,0);
        for(int i = 0; i < N; i++){
            SH[i+1] = SH[i] + A_desc[i];
            SL[i+1] = SL[i] + A_asc[i];
        }
        map<ll,int> freq;
        for(ll x : A) freq[x]++;

        int ans = 0;
        int prefix_more = 0;
        for(auto it = freq.rbegin(); it != freq.rend(); ++it){
            ll v = it->first;
            int cnt_eq = it->second;
            int cnt_more = prefix_more;
            int cnt_lt = N - cnt_more - cnt_eq;
            ll sum_lt = SL[cnt_lt];
            ll D = sum_lt - v * (ll)cnt_lt;
            ll R = -D;
            int low = 0, high = cnt_more, best = -1;
            while(low <= high){
                int mid = (low + high) >> 1;
                ll fh = SH[mid] - (ll)mid * v;
                if(fh < R){
                    best = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            int m_max = (best >= 0 ? cnt_eq + best : 0);
            ans = max(ans, m_max);
            prefix_more += cnt_eq;
        }
        cout << ans << "\n";
    }
    return 0;
}

Submission Info

Judge Result