Table of Contents

ExplanationImplementation

Official Analysis (C++ and Java)

Explanation

Since there are only 33 cows and N≤1000N \leq 1000, we can sort all of the entries by date and update the selected cow's milk value for each entry.

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N), as the number of cows is constant.

C++

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


const vector<string> NAMES{"Bessie", "Elsie", "Mildred"};
const int START_AMT = 7;


int main() {
	freopen("measurement.in", "r", stdin);


	int update_num;

Java

import java.io.*;
import java.util.*;


public class Measurement {
	static final String[] NAMES = new String[] {"Bessie", "Elsie", "Mildred"};
	static final int START_AMT = 7;


 	Code Snippet: Update Class (Click to expand)


	public static void main(String[] args) throws IOException {

Python

NAMES = ["Bessie", "Elsie", "Mildred"]
START_AMT = 7


with open("measurement.in") as read:
	update_num = int(read.readline())
	updates = []
	for _ in range(update_num):
		day, cow, change = read.readline().split()
		updates.append((int(day), cow, int(change)))

Cow Starting Amounts

You might have noticed that since we only keep track of the relative orders of the cows, the starting amount each cow produces doesn't matter at all. It could be 0, 9, or even -100, and the code would still produce the correct output.

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