Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.example.interviewprep.vizrt;
- import java.io.*;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.StringTokenizer;
- public class Coffee {
- public static void main(String[] args) throws IOException {
- try (Reader reader = new Reader();
- PrintWriter out = new PrintWriter(System.out)) {
- int l, a, b, t, r, n;
- l = reader.nextInt();
- a = reader.nextInt();
- b = reader.nextInt();
- t = reader.nextInt();
- r = reader.nextInt();
- n = reader.nextInt();
- if (n == 0) {
- out.println(0);
- return;
- }
- int[] shops = new int[n];
- int[][] intervals = new int[n][3];
- int next[] = new int[n];
- Arrays.fill(next, -1);
- for (int i = 0; i < n; i++) shops[i] = reader.nextInt();
- int right = 0;
- for (int i = 0; i < n; i++) {
- int x = Math.min(shops[i] + a * t, l);
- int y = Math.min(x + b * r, l);
- intervals[i][0] = shops[i];
- intervals[i][1] = x;
- intervals[i][2] = y;
- }
- for (int i = 0; i < n; i++) {
- if (right == n) next[i] = n;
- else {
- right = Math.max(right, i + 1);
- while (right < n && shops[right] >= intervals[i][0] && shops[right] <= intervals[i][2]) {
- right++;
- }
- next[i] = right - 1;
- if (next[i] == i) next[i] = -1;
- }
- }
- int dp[] = new int[n + 1];
- Arrays.fill(dp, -1);
- rec(0, intervals, next, n, dp); // pos , flag -> 1 means must take , 0 means optional
- List<Integer> ans = new ArrayList<>();
- printPath(0, intervals, next, n, dp, ans);
- out.println(ans.size());
- boolean space = false;
- for (int an : ans) {
- if (space) out.print(" ");
- out.print(an);
- space = true;
- }
- out.println("");
- }
- }
- private static void printPath(int pos, int[][] intervals, int[] next, int n, int[] dp, List<Integer> ans) {
- if (pos >= n) return;
- ans.add(pos);
- int nxt = next[pos];
- if (nxt == -1) {
- printPath(pos + 1, intervals, next, n, dp, ans);
- } else if (nxt < n) {
- int opta = Math.max(0, intervals[nxt][0] - intervals[pos][1]) + rec(nxt, intervals, next, n, dp);
- int optb = intervals[pos][2] - intervals[pos][1] + rec(nxt + 1, intervals, next, n, dp);
- if (opta > optb) printPath(nxt, intervals, next, n, dp, ans);
- else {
- printPath(nxt + 1, intervals, next, n, dp, ans);
- }
- }
- }
- private static int rec(int pos, int[][] intervals, int[] next, int n, int[] dp) {
- if (pos >= n) {
- return 0;
- }
- if (dp[pos] != -1) return dp[pos];
- int nxt = next[pos];
- if (nxt == -1) {
- return dp[pos] = intervals[pos][2] - intervals[pos][1] + rec(pos + 1, intervals, next, n, dp);
- } else if (nxt < n) {
- int opta = Math.max(0, intervals[nxt][0] - intervals[pos][1]) + rec(nxt, intervals, next, n, dp);
- int optb = intervals[pos][2] - intervals[pos][1] + rec(nxt + 1, intervals, next, n, dp);
- return dp[pos] = Math.max(opta, optb);
- } else {
- return dp[pos] = intervals[pos][2] - intervals[pos][1];
- }
- }
- 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