Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import javax.imageio.plugins.jpeg.JPEGImageReadParam;
- import javax.print.attribute.standard.MediaSize;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- public class Road {
- public static void main(String[] args) throws IOException {
- BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer tokenizer = new StringTokenizer(f.readLine());
- int n = Integer.parseInt(tokenizer.nextToken());
- int m = Integer.parseInt(tokenizer.nextToken());
- tokenizer = new StringTokenizer(f.readLine());
- int[][] distanceTo = new int[m][2];
- int[] islands = new int[m];
- for (int i = 0; i < m; i++) {
- islands[i] = Integer.parseInt(tokenizer.nextToken());
- }
- Arrays.sort(islands);
- distanceTo[0][1] = islands[1];
- distanceTo[m - 1][0] = islands[m - 1] - islands[m - 2];
- for (int i = 1; i < m - 1; i++) {
- distanceTo[i][0] = islands[i] - islands[i - 1];
- distanceTo[i][1] = islands[i + 1] - islands[i];
- }
- int[] distanceToLast = new int[m - 1];
- for (int i = 0; i < m - 1; i++) {
- distanceToLast[i] = islands[m - 1] - islands[i];
- }
- tokenizer = new StringTokenizer(f.readLine());
- int g = Integer.parseInt(tokenizer.nextToken());
- int r = Integer.parseInt(tokenizer.nextToken());
- islands = null;
- int[][] dp = new int[m][g + 1];
- for (int i = 0; i < m; i++) {
- Arrays.fill(dp[i], Integer.MAX_VALUE);
- }
- dp[0][0] = 0;
- Island start = new Island(0, 0, 0);
- PriorityQueue<Island> toCheck = new PriorityQueue<Island>();
- boolean[][] visited = new boolean[m][g + 1];
- toCheck.add(start);
- int minPossibleTimeSoFar = Integer.MAX_VALUE;
- while (!toCheck.isEmpty()) {
- Island island = toCheck.poll();
- if (visited[island.island][island.modTime]) {
- continue;
- }
- /*
- if (island.island == m - 1) {
- System.out.println(island.time);
- return;
- } */
- visited[island.island][island.modTime] = true;
- minPossibleTimeSoFar = Math.min(distanceToLast[island.island] + island.time, minPossibleTimeSoFar);
- if (island.modTime == g) {
- int time = r + island.time;
- if (time < dp[island.island][0]) {
- dp[island.island][0] = time;
- toCheck.add(new Island(island.island, time, 0));
- }
- } else {
- if (island.modTime + distanceToLast[island.island] <= g && island.time + distanceToLast[island.island] <= minPossibleTimeSoFar) {
- System.out.println(island.time + distanceToLast[island.island]);
- return;
- }
- int modTime = island.modTime + distanceTo[island.island][1];
- if (island.island != m - 1 && modTime <= g) {
- int time = island.time + distanceTo[island.island][1];
- if (island.island + 1 == m - 1) {
- System.out.println(time);
- return;
- }
- if (time < dp[island.island + 1][modTime]) {
- dp[island.island + 1][modTime] = time;
- toCheck.add(new Island(island.island + 1, time, modTime));
- }
- }
- modTime = island.modTime + distanceTo[island.island][0];
- if (island.island != 0 && modTime <= g) {
- int time = island.time + distanceTo[island.island][0];
- if (time < dp[island.island - 1][modTime]) {
- dp[island.island - 1][modTime] = time;
- toCheck.add(new Island(island.island - 1, time, modTime));
- }
- }
- }
- }
- System.out.println(-1);
- }
- private static class Island implements Comparable<Island> {
- int time;
- int modTime;
- int island;
- public Island(int island, int time, int modTime) {
- this.island = island;
- this.time = time;
- this.modTime = modTime;
- }
- @Override
- public int compareTo(Island island) {
- if (this.time < island.time) {
- return -1;
- } else if (this.time > island.time) {
- return 1;
- }
- return 0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement