Hi,
My question is about the 2018 january silver problem rental services.
My code is below. My code only works for 2 test cases. Can someone help explain why my code is fails on almost all the test cases and where it is wrong?
import java.io.;
import java.util.;
public class submission {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new FileReader("rental.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("rental.out")));
// BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
Long [] cows = new Long[n];
Store [] stores = new Store[m];
Long [] rentprices = new Long[r];
for (int i = 0; i < n; i++) {
cows[i] = Long.parseLong(bf.readLine());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(bf.readLine());
int gals = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
stores[i] = new Store(gals, p);
}
for (int i = 0; i < r; i++) {
rentprices[i] = Long.parseLong(bf.readLine());
}
Arrays.sort(cows, Comparator.reverseOrder());
Arrays.sort(stores, Comparator.reverseOrder());
Arrays.sort(rentprices, Comparator.reverseOrder());
int psums [] = new int[r+1];
for (int i = 1; i <= r; i++) {
psums[i] += (psums[i-1] + rentprices[i-1]);
}
int currentstore = 0;
long sold = 0;
long ans = psums[r-Math.min(n, r)];
for (int i = 0; i < n; i++) {
while (cows[i] > 0 && currentstore < m) {
if (stores[currentstore].gals <= cows[i]) {
sold += (stores[currentstore].gals * stores[currentstore].price);
cows[i] -= stores[currentstore].gals;
currentstore++;
}
else {
sold += (stores[currentstore].price * cows[i]);
stores[currentstore].gals -= cows[i];
// System.out.println(stores[currentstore].gals);
cows[i] = (long) 0;
}
}
ans = Math.max(ans, sold + (i == n-1?0:psums[r-Math.min(i, r)]));
}
out.println(ans);
out.close();
bf.close();
}
static class Store implements Comparable<Store>{
public int gals, price;
public Store(int x, int y) {
gals = x;
price = y;
}
public int compareTo(Store s) {
return price-s.price;
}
}
}
Please format your code, explain it, and tell us what you have tried first.
I have formatted my code below. Hopefully it is not too hard to read.
What the code is supposed to do is first sort in reverse order the amount of milk that each cows can produce, the stores by price, and the rents. Then I make a prefix sum of rents. Then I do a linear search of the possible combinations of how many cows to sell and how many cows to rent. I find the total amount of money made by FJ and then take the max to find the answer. This code does not work as intended though. Where does is the mistake in the code?
import java.io.;
import java.util.;
public class submission {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new FileReader("rental.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("rental.out")));
// BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
Long [] cows = new Long[n];
Store [] stores = new Store[m];
Long [] rentprices = new Long[r];
for (int i = 0; i < n; i++) {
cows[i] = Long.parseLong(bf.readLine());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(bf.readLine());
int gals = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
stores[i] = new Store(gals, p);
}
for (int i = 0; i < r; i++) {
rentprices[i] = Long.parseLong(bf.readLine());
}
Arrays.sort(cows, Comparator.reverseOrder());
Arrays.sort(stores, Comparator.reverseOrder());
Arrays.sort(rentprices, Comparator.reverseOrder());
int psums [] = new int[r+1];
for (int i = 1; i <= r; i++) {
psums[i] += (psums[i-1] + rentprices[i-1]);
}
int currentstore = 0;
long sold = 0;
long ans = psums[r-Math.min(n, r)];
for (int i = 0; i < n; i++) {
while (cows[i] > 0 && currentstore < m) {
if (stores[currentstore].gals <= cows[i]) {
sold += (stores[currentstore].gals * stores[currentstore].price);
cows[i] -= stores[currentstore].gals;
currentstore++;
}
else {
sold += (stores[currentstore].price * cows[i]);
stores[currentstore].gals -= cows[i];
// System.out.println(stores[currentstore].gals);
cows[i] = (long) 0;
}
}
ans = Math.max(ans, sold + (i == n-1?0:psums[r-Math.min(i, r)]));
}
out.println(ans);
out.close();
bf.close();
}
static class Store implements Comparable<Store>{
public int gals, price;
public Store(int x, int y) {
gals = x;
price = y;
}
public int compareTo(Store s) {
return price-s.price;
}
}
}