najimCseJu

Untitled

Oct 5th, 2019
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.00 KB | None | 0 0
  1. package com.example.interviewprep.vizrt;
  2.  
  3. import java.io.*;
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.List;
  7. import java.util.StringTokenizer;
  8.  
  9. public class Coffee {
  10.  
  11.  
  12.     public static void main(String[] args) throws IOException {
  13.         try (Reader reader = new Reader();
  14.              PrintWriter out = new PrintWriter(System.out)) {
  15.             int l, a, b, t, r, n;
  16.             l = reader.nextInt();
  17.             a = reader.nextInt();
  18.             b = reader.nextInt();
  19.             t = reader.nextInt();
  20.             r = reader.nextInt();
  21.             n = reader.nextInt();
  22.             if (n == 0) {
  23.                 out.println(0);
  24.                 return;
  25.             }
  26.             int[] shops = new int[n];
  27.             int[][] intervals = new int[n][3];
  28.             int next[] = new int[n];
  29.             Arrays.fill(next, -1);
  30.             for (int i = 0; i < n; i++) shops[i] = reader.nextInt();
  31.             int right = 0;
  32.             for (int i = 0; i < n; i++) {
  33.                 int x = Math.min(shops[i] + a * t, l);
  34.                 int y = Math.min(x + b * r, l);
  35.                 intervals[i][0] = shops[i];
  36.                 intervals[i][1] = x;
  37.                 intervals[i][2] = y;
  38.             }
  39.             for (int i = 0; i < n; i++) {
  40.                 if (right == n) next[i] = n;
  41.                 else {
  42.                     right = Math.max(right, i + 1);
  43.                     while (right < n && shops[right] >= intervals[i][0] && shops[right] <= intervals[i][2]) {
  44.                         right++;
  45.                     }
  46.                     next[i] = right - 1;
  47.                     if (next[i] == i) next[i] = -1;
  48.                 }
  49.             }
  50.             int dp[] = new int[n + 1];
  51.             Arrays.fill(dp, -1);
  52.             rec(0, intervals, next, n, dp); // pos , flag -> 1 means must take , 0 means optional
  53.             List<Integer> ans = new ArrayList<>();
  54.             printPath(0, intervals, next, n, dp, ans);
  55.             out.println(ans.size());
  56.             boolean space = false;
  57.             for (int an : ans) {
  58.                 if (space) out.print(" ");
  59.                 out.print(an);
  60.                 space = true;
  61.             }
  62.             out.println("");
  63.         }
  64.     }
  65.  
  66.     private static void printPath(int pos, int[][] intervals, int[] next, int n, int[] dp, List<Integer> ans) {
  67.         if (pos >= n) return;
  68.         ans.add(pos);
  69.         int nxt = next[pos];
  70.         if (nxt == -1) {
  71.             printPath(pos + 1, intervals, next, n, dp, ans);
  72.         } else if (nxt < n) {
  73.             int opta = Math.max(0, intervals[nxt][0] - intervals[pos][1]) + rec(nxt, intervals, next, n, dp);
  74.             int optb = intervals[pos][2] - intervals[pos][1] + rec(nxt + 1, intervals, next, n, dp);
  75.             if (opta > optb) printPath(nxt, intervals, next, n, dp, ans);
  76.             else {
  77.                 printPath(nxt + 1, intervals, next, n, dp, ans);
  78.             }
  79.         }
  80.     }
  81.  
  82.  
  83.     private static int rec(int pos, int[][] intervals, int[] next, int n, int[] dp) {
  84.         if (pos >= n) {
  85.             return 0;
  86.         }
  87.         if (dp[pos] != -1) return dp[pos];
  88.         int nxt = next[pos];
  89.         if (nxt == -1) {
  90.             return dp[pos] = intervals[pos][2] - intervals[pos][1] + rec(pos + 1, intervals, next, n, dp);
  91.  
  92.         } else if (nxt < n) {
  93.             int opta = Math.max(0, intervals[nxt][0] - intervals[pos][1]) + rec(nxt, intervals, next, n, dp);
  94.             int optb = intervals[pos][2] - intervals[pos][1] + rec(nxt + 1, intervals, next, n, dp);
  95.             return dp[pos] = Math.max(opta, optb);
  96.         } else {
  97.             return dp[pos] = intervals[pos][2] - intervals[pos][1];
  98.         }
  99.     }
  100.  
  101.  
  102.     public static class Reader implements Closeable {
  103.         public BufferedReader reader;
  104.         public StringTokenizer tokenizer;
  105.  
  106.         public Reader() {
  107.             reader = new BufferedReader(new InputStreamReader(System.in), 32768);
  108.             tokenizer = null;
  109.         }
  110.  
  111.         public Reader(String filePath) throws FileNotFoundException {
  112.             reader = new BufferedReader(new FileReader(filePath), 32768);
  113.             tokenizer = null;
  114.         }
  115.  
  116.         public String next() {
  117.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  118.                 try {
  119.                     tokenizer = new StringTokenizer(reader.readLine());
  120.                 } catch (IOException e) {
  121.                     throw new RuntimeException(e);
  122.                 }
  123.             }
  124.             return tokenizer.nextToken();
  125.         }
  126.  
  127.         public String nextLine() throws IOException {
  128.             return reader.readLine();
  129.         }
  130.  
  131.         public int nextInt() {
  132.             return Integer.parseInt(next());
  133.         }
  134.  
  135.         public long nextLong() {
  136.             return Long.parseLong(next());
  137.         }
  138.  
  139.         @Override
  140.         public void close() throws IOException {
  141.             this.reader.close();
  142.         }
  143.     }
  144.     /** ***************Helper Methods Ends Here****** */
  145.  
  146.  
  147. }
Advertisement
Add Comment
Please, Sign In to add comment