Hello, I am stuck on the January 2018 problem Rental Service, essentially what I am trying to do is simulate buying each cow and renting each cow and then taking the maximum value between each simulation and adding it. However, my code only seems to be passing the first test case.
My code:
import java.io.*;
import java.util.*;
public class rental {
static class InputReader {
BufferedReader reader;
StringTokenizer tokenizer;
public InputReader(File stream) throws FileNotFoundException {
reader = new BufferedReader(new FileReader(stream), 32768);
tokenizer = null;
}
String next() { // reads in the next string
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
} // reads in the next int
public long nextLong() {
return Long.parseLong(next());
} // reads in the next long
public char nextChar() {
return (next().charAt(0));
} // reads in the next int
public double nextDouble() {
return Double.parseDouble(next());
} // reads in the next double
}
static InputReader sc;
static {
try {
sc = new InputReader(new File("rental.in"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
static class Pair{
long a, b;
public Pair(long a, long b){
this.a = a; //price
this.b = b; //capacity remaining
}
}
static class renterComp implements Comparator<Pair>{
@Override
public int compare(Pair o1, Pair o2) {
if(o1.b == 0){
return 1;
}
if(o2.b == 0){
return - 1;
}
return Long.compare(o2.a, o1.a);
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("rental.out")));
int n = sc.nextInt(); int m = sc.nextInt(); int r = sc.nextInt(); long ans = 0;
long [] cows = new long [n]; TreeSet<Pair> renters = new TreeSet<>(new renterComp());
LinkedList<Long> buyers = new LinkedList<>();
for (int i = 0; i < n; i++) {
cows[i] = sc.nextLong();
}
for (int i = 0; i < m; i++) {
long c = sc.nextLong();
long p = sc.nextLong();
renters.add(new Pair(p, c));
}
for (int i = 0; i < r; i++) {
buyers.add(sc.nextLong());
}
// simulate the buying of cows
Collections.sort(buyers, new Comparator<Long>() {
@Override
public int compare(Long o1, Long o2) {
return Long.compare(o2, o1);
}
});
Arrays.sort(cows);
long [] cowProfitWhenBuying = new long[n];
for (int i = n - 1; i >= 0; i--) {
if(i >= buyers.size())
cowProfitWhenBuying[i] = 0;
else
cowProfitWhenBuying[i] = buyers.get(i);
}
// simulate the renting of the cows
boolean rentersRemaining = false;
long [] cowsProfitWhenRenting = new long[n];
for (int i = n - 1; i >= 0; i--) {
if(rentersRemaining)
break;
else {
while (cows[i] > 0) {
Pair p = renters.pollFirst();
if(p.b <= 0) {
rentersRemaining = true;
break;
}
long capacityToAdd = Math.min(p.b, cows[i]);
cowsProfitWhenRenting[i] += capacityToAdd * p.a;
cows[i] -= capacityToAdd;
renters.add(new Pair(p.a, p.b - capacityToAdd));
}
}
}
for (int j = 0; j < n; j++) {
ans += Math.max(cowProfitWhenBuying[j], cowsProfitWhenRenting[j]);
}
out.println(ans);
out.close();
}
}