Team Building 2#12411

Team Building 2 (Həll təhlili)

Problem Author:	turneja
Prepared by:	turneja
Edited by:	turneja

Solution

Since there can be only one coach, let us quickly calculate for each person $i$ the best answer when $i$ is selected as the coach and then take the maximum over that. First sort the people by their playing strengths and let $S$ be the sum of the largest $k$ values of playing strengths. Then if the person selected as the coach is not in the $k$ people with the largest playing strengths the answer is simply $S \cdot c_{i}$ S\cdot c_i. Otherwise subtract the coach's playing strength from $S$ and add to it the playing strength of the $k + 1$ k+1-th strongest person. The time complexity of this approach is $O (n lo g n)$ \mathcal{O}(n \log n).

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);



int main() {
    IOS;
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        assert(n >= 2 && k >= 1 && k < n);
        vector<pair<int, int>> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i].first;
        }
        for (int i = 0; i < n; i++) {
            cin >> a[i].second;
        }
        sort(a.begin(), a.end());
        reverse(a.begin(), a.end());
        ll s = 0, ans = 0;
        for (int i = 0; i < k; i++) {
            s += a[i].first;
        }
        for (int i = 0; i < n; i++) {
            if (i < k) {
                ans = max(ans, (s - a[i].first + a[k].first) * a[i].second);
            } else {
                ans = max(ans, s * a[i].second);
            }
        }
        cout << ans << endl;


    }
    return 0;
}

C++