View difference between Paste ID: JnA7LMZS and mjFmkHsx
SHOW: | | - or go back to the newest paste.
1
2
import java.util.Arrays;
3
import java.util.Scanner;
4
5
public class Solution {
6
	static int gasStations;
7
	static Long maxFuel;
8
	static Long startingFuel;
9
	static Long length;
10
11
	private static class Station implements Comparable<Station> {
12
		long  price;
13
		long  pos;
14
15
		private Station(long  price, long pos) {
16
			this.price = price;
17
			this.pos = pos;
18
		}
19
20
		@Override
21
		public int compareTo(Station o) {
22
			return Long.valueOf(price).compareTo(o.price);
23
		}
24
25
		@Override
26
		public String toString() {
27
			return "{" + price + "$, " + pos + "}";
28
		}
29
	}
30
31
	public static void main(String[] args) {
32
		Scanner scanner = new Scanner(System.in);
33
		int M = Integer.parseInt(scanner.nextLine());
34
		for (int i = 0; i < M; i++) {
35
			String[] line = scanner.nextLine().split("\\s+");
36
			gasStations = Integer.parseInt(line[0]);
37
			maxFuel = Long.parseLong(line[1]);
38
			startingFuel = Long.parseLong(line[2]);
39
			length = Long.parseLong(line[3]);
40
			Station[] stations = new Station[gasStations];
41
			for (int s = 0; s < gasStations; s++) {
42
				line = scanner.nextLine().split("\\s+");
43
				stations[s] = new Station(Long.parseLong(line[1]), Long.parseLong(line[0]));
44
			}
45
            //SORTING STATIONS, CHEAPEST FIRST
46
			Arrays.sort(stations);
47
			checkSolution(stations);
48
		}
49
50
	}
51
52
	private static void checkSolution(Station[] stations) {
53
		long[] reserveFuel = {0};
54
		System.out.println(recursiveCall(0, length, startingFuel, stations, reserveFuel));
55
	}
56
57
    	// RETURNS THE $$ SPENT IN FUEL
58-
    // RETURNS THE $$ SPENT IN FUEL
58+
	// PARAMS: 
59
	// 	START: the start point of this part of the trip
60
	// 	END: the goal of this part of the trip 
61-
        // IF I HAVE ENOUGH FUEL TO GET TO THE END
61+
        //	FUEL: the amount of fuel I have for this section
62
	// 	STATIONS: all the stations, nulled out the ones I have been to
63
	//	RESERVE FUEL: pointer used to return the amount of gas that was left after the trip. /*I'm not proud of this*/
64
	private static long recursiveCall(long start, long end, long fuel, Station[] stations, long [] reserveFuel) {
65
//		System.out.println("RECURSIVING -- start:" + start + " end:" + end + " fuel:" + fuel);
66
        	// IF I HAVE ENOUGH FUEL TO GET TO THE END
67
		if (end - start <= fuel) {
68
			reserveFuel[0] = fuel - (end - start);
69-
            // GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS
69+
70
		}
71
72
		Station station = null;
73
		for (int s = 0; s < gasStations && station == null; s++) {
74
            	// GET THE FIRST (AND CHEAPEST) STATION BETWEEN MY CURRENT START AND END POSITIONS
75-
        // THERE ARE NO STATIONS BETWEEN START AND END 
75+
76
				station = stations[s];
77
				stations[s] = null; //NULLING OUT USED STATIONS
78
			}
79
		}
80
	        // THERE ARE NO STATIONS BETWEEN START AND END 
81-
        long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel);
81+
82-
        // IF I COULDN'T MAKE IT
82+
83
		}
84
		long ans = 0; // TOTAL $ SPENT
85
86-
        ans += var; // ADDING THE $$ NEEDED TO GET HERE
86+
	        long var = recursiveCall(start, station.pos, fuel, stations, reserveFuel);
87
        	// IF I COULDN'T MAKE IT
88-
        long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]);
88+
89
			return var;
90-
        long chargedFuel = reserveFuel[0] + neededFuel;
90+
91
	        ans += var; // ADDING THE $$ NEEDED TO GET HERE
92
93
        	long neededFuel = Math.min(maxFuel- reserveFuel[0], end - station.pos - reserveFuel[0]);
94
95
	        long chargedFuel = reserveFuel[0] + neededFuel;
96-
        // IF I COULDN'T MAKE IT
96+
97
        
98
//		System.out.println("CHARGING FUEL -- $" + (neededFuel * station.price) + " in:" + station.pos);
99
		reserveFuel[0] = 0;
100-
        ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL        
100+
101
	        // IF I COULDN'T MAKE IT
102
		if(var == -1)
103
			return var;
104
105
	        ans += var; // ADDING WHAT I WILL SPEND IN THE REST OF THE TRIP TO MY GOAL        
106
		return ans;
107
	}
108
}