USACO 2022 December Contest Bronze Division - Cow College

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

First, only the values from the arrays can be optimal as far as choosing tuition values go.

Then, we can sort the cows and find out for each value the number of cows greater than it and find the maximum answer in that way.

Source codes

The source codes in C++ and Python can be seen below.

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

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

    int n;
    cin >> n;

    vector<int> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    sort(v.begin() + 1, v.begin() + n + 1);

    long long maxi = 0;
    long long tuition = 0;
    for(int i = 1; i <= n; i++)
        if(1LL * (n - i + 1) * v[i] > maxi)
            maxi = 1LL * (n - i + 1) * v[i], tuition = v[i];

    cout << maxi << " " << tuition << '\n';
    return 0;
}

n = int(input())
v = list(map(int, input().split()))
v.sort()
maxi = 0
tuition = 0
for i in range(n):
    current = (n - i) * v[i]
    if current > maxi:
        maxi = current
        tuition = v[i]
print(maxi, tuition)