Editorial for 20B Rating


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

To get the highest possible rating of a person, we get the person who has the highest rating now. Then he/she play \(M\) matches with people. We can simply say that he/she wins all the matches so that his/her score will be maximum.

The only issue that we will encounter is that when matches he/she play are with a competitor who has lower than \(K\) points. To fix this:

  • He/she will first play with people who have more than \(K\) points till the person has lower than \(K\) points or no more matches left.
  • He/she will play with people in the decreasing order of their score.
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int siz = 300005;

ll arr[siz];
ll n, m, k, l, res;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin>>n>>k>>m;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(arr, arr+n);
    n--;
    for(int i=n-1;i>=0;i--){
        if(m==0) break;
        if(arr[i]<k) break;
        while(arr[i]>=k){
            arr[i]-=k;
            arr[n]+=k;
            m--;
        }
    }
    sort(arr, arr+n);

    for(int i=n-1;i>=0;i--){
        if(m==0) break;
        m--;
        arr[n]+=arr[i];
    }
    cout<<arr[n];

}