Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.example.interviewprep.vizrt;
- import java.io.*;
- import java.util.*;
- public class Coffee_ITR {
- public static void main(String[] args) throws IOException {
- try (Reader reader = new Reader();
- PrintWriter out = new PrintWriter(System.out)) {
- long l;
- int a, b, t, r, n;
- l = reader.nextLong();
- a = reader.nextInt();
- b = reader.nextInt();
- t = reader.nextInt();
- r = reader.nextInt();
- n = reader.nextInt();
- if (n == 0) {
- out.println(0);
- return;
- }
- long[][] intervals = new long[n + 1][3]; // 12MB
- int next[] = new int[n];// 1 MB
- Arrays.fill(next, -1);
- for (int i = 0; i < n; i++) intervals[i][0] = reader.nextLong();
- for (int i = 0; i < n; i++) {
- long x = intervals[i][0] + a * t;
- long y = x + b * r;
- intervals[i][1] = Math.min(x, l);
- intervals[i][2] = Math.min(y, l);
- }
- intervals[n][0] = intervals[n][1] = intervals[n][2] = l;
- /*
- * Finding rightmost coffee shop that intersects with current shops interval
- * Two pointer approach, Complexity O(n)
- * */
- int right = 0;
- for (int i = 0; i < n; i++) {
- right = Math.max(right, i + 1);
- while (right < n && intervals[right][0] >= intervals[i][0] && intervals[right][0] <= intervals[i][2]) {
- right++;
- }
- next[i] = right - 1;
- if (next[i] == i) next[i] = -1;
- }
- long dp[] = new long[n + 1]; // 4MB
- dp[n] = 0;
- int nextPos[] = new int[n + 1];
- for (int i = n - 1; i >= 0; i--) {
- if (next[i] == -1) {
- dp[i] = dp[i + 1] + intervals[i][2] - intervals[i][1];
- nextPos[i] = i + 1;
- } else {
- long op1 = dp[next[i]] + Math.max(0, Math.min(intervals[next[i]][0], intervals[i][2]) - intervals[i][1]);
- long op2 = dp[next[i] + 1] + intervals[i][2] - intervals[i][1];
- if (op1 > op2) {
- dp[i] = op1;
- nextPos[i] = next[i];
- } else {
- dp[i] = op2;
- nextPos[i] = next[i] + 1;
- }
- }
- }
- LinkedList<Integer> ans = new LinkedList<>();
- int p = 0;
- while (p != n) {
- ans.addLast(p);
- p = nextPos[p];
- }
- boolean isSpace = false;
- out.println(ans.size());
- for (int an : ans) {
- if (isSpace) out.print(" ");
- out.print(an);
- isSpace = true;
- }
- }
- }
- public static class Reader implements Closeable {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public Reader() {
- reader = new BufferedReader(new InputStreamReader(System.in), 32768);
- tokenizer = null;
- }
- public Reader(String filePath) throws FileNotFoundException {
- reader = new BufferedReader(new FileReader(filePath), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public String nextLine() throws IOException {
- return reader.readLine();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- @Override
- public void close() throws IOException {
- this.reader.close();
- }
- }
- /** ***************Helper Methods Ends Here****** */
- }
Advertisement
Add Comment
Please, Sign In to add comment