2018-1A Problem B

Final solution

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Cashier struct {
	M int
	S int
	P int
}

func test() {
	var R, B, C int
	mustReadLineOfInts(&R, &B, &C)
	cashiers := make([]Cashier, 0, C)
	minimumP := -1
	maxTime := 0
	for i := 0; i < C; i++ {
		var M, S, P int
		mustReadLineOfInts(&M, &S, &P)
		cashiers = append(cashiers, Cashier{M, S, P})
		if minimumP == -1 {
			minimumP = P
		} else if minimumP > P {
			minimumP = P
		}
		for _, cashier := range cashiers {
			thisMaxTime := cashier.P + cashier.S*cashier.M
			if maxTime < thisMaxTime {
				maxTime = thisMaxTime
			}
		}
	}
	tLeast := sort.Search(maxTime+1, func(t int) bool { // canFinishWithin t
		if t < minimumP {
			return false
		}
		cashiersCanDo := make([]int, 0, len(cashiers))
		for _, cashier := range cashiers {
			if t < cashier.P {
				cashiersCanDo = append(cashiersCanDo, 0)
				continue
			}
			canDo := (t - cashier.P) / cashier.S
			if canDo > cashier.M {
				canDo = cashier.M
			}
			cashiersCanDo = append(cashiersCanDo, canDo)
		}
		sort.Ints(cashiersCanDo)
		sumCanDos := 0
		for useNCashiers := 1; useNCashiers <= len(cashiers) && useNCashiers <= R; useNCashiers++ {
			sumCanDos += cashiersCanDo[len(cashiersCanDo)-useNCashiers]
			if sumCanDos >= B {
				return true
			}
		}
		return false
	})
	stdout.WriteString(fmt.Sprintf("%d\n", tLeast))
}

// boilerplate omitted...

Sample test cases given in question

3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1

Other files

2
1 1 1
100 1 1
3 7 3
3 2 20
3 5 6
4 8 1