Official Analysis (C++, Java, Python)

Solution

Explanation

The main issue in this problem is figuring out how to efficiently calculate the amount of money FJ earns.

To do this, we can sort our list of cows before starting to process them. In our sorted list, notice that the amount of tuition FJ earns at index ii (starting from 0) is ci⋅(N−i)c_i \cdot (N-i).

For example, let's look at the sample input:

4
1 6 4 6

If we sort the list so it becomes [1,4,6,6][1, 4, 6, 6] and take ii to be 11, FJ will earn c1⋅(N−1)=4⋅3=12c_1 \cdot (N-1)=4 \cdot 3=12 units of money.

With this knowledge, we can now iterate through the list, trying all values of ii and taking the maximum tuition FJ earns.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N)

C++

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


int main() {
	int n;
	cin >> n;
	vector<int> tuition(n);
	for (int &t : tuition) { cin >> t; }


	sort(tuition.begin(), tuition.end());

Java

import java.util.*;


public class CowCollege {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int[] tuition = new int[n];
		for (int i = 0; i < n; i++) { tuition[i] = sc.nextInt(); }

Python

n = int(input())
tuition = sorted(map(int, input().split()))


best_tuition = 0
best_money = 0
for i in range(n):
	# Apply the formula from the editorial
	curr_tuition = tuition[i] * (n - i)
	if curr_tuition > best_money:
		best_tuition = tuition[i]
		best_money = curr_tuition


print(best_money, best_tuition)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum