Guest User

Untitled

a guest
Sep 12th, 2017
185
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     static class ConvexHullTrick {
  2.        
  3.         static final long NEGATIVE_INF = -100L * 1000 * 1000 * 1000;
  4.        
  5.         static class Line {
  6.             long k, b;
  7.             long xNumerator, xDenominator;
  8.  
  9.             public Line(long k, long b, long xNumerator, long xDenominator) {
  10.                 super();
  11.                 this.k = k;
  12.                 this.b = b;
  13.                
  14.                 this.xNumerator = xNumerator;
  15.                 this.xDenominator = xDenominator;
  16.             }
  17.            
  18.             double x() {
  19.                 return xNumerator * 1.0 / xDenominator;
  20.             }
  21.         }
  22.        
  23.         Line[] stack;
  24.         int size;
  25.        
  26.         ConvexHullTrick(int size, long baseB) {
  27.             stack = new Line[size + 10];
  28.             size = 0;
  29.            
  30.             __insert(0, baseB, NEGATIVE_INF - 10, 1);
  31.         }
  32.        
  33.         private void __insert(long k, long b, long xNumerator, long xDenominator) {
  34.             stack[size++] = new Line(k, b, xNumerator, xDenominator);
  35.         }
  36.        
  37.         void updateStack(long nextHeight) {
  38.             while (size > 1) {
  39.                 Line lastLine = stack[size - 1];
  40.                 if (lastLine.k >= nextHeight) {
  41.                     --size;
  42.                     stack[size] = null;
  43.                 } else {
  44.                     break;
  45.                 }
  46.             }
  47.         }
  48.        
  49.         long getBest(long x) {
  50.             int result = 0;
  51.            
  52.             for (int left = 1, right = size - 1; left <= right; ) {
  53.                 int mid = (left + right) >> 1;
  54.                 Line line = stack[mid];
  55.                
  56.                 if (line.x() <= x) {
  57.                     result = mid;
  58.                     left = mid + 1;
  59.                 } else {
  60.                     right = mid - 1;
  61.                 }
  62.             }
  63.            
  64.             Line line = stack[result];
  65.             return line.k * x + line.b;
  66.         }
  67.        
  68.         void addLine(int index, long k, long b) {
  69.             while (size > 1) {             
  70.                 Line line = stack[size - 1];
  71.                
  72.                 if (line.k == k) {
  73.                     --size;
  74.                     stack[size] = null;
  75.                    
  76.                     continue;
  77.                 }
  78.                
  79.                 long lastXNumerator = (b - line.b);
  80.                 long lastXDenominator = (line.k - k);
  81.                
  82.                 double lastX = lastXNumerator * 1.0 / lastXDenominator;
  83.                
  84.                 if (lastX > line.x()) {
  85.                     __insert(k, b, lastXNumerator, lastXDenominator);
  86.                     return;
  87.                 } else {
  88.                     --size;
  89.                     stack[size] = null;
  90.                 }
  91.             }
  92.            
  93.             __insert(k, b, NEGATIVE_INF + index, 1);
  94.         }
  95.     }
  96.    
  97.     static long getAnswer(int[] a, int k) {    
  98.         IntIndexPair[] iip = IntIndexPair.from(a);
  99.         Arrays.sort(iip, new Comparator<IntIndexPair>() {
  100.  
  101.             @Override
  102.             public int compare(IntIndexPair a, IntIndexPair b) {
  103.                 if (a.value != b.value) {
  104.                     return a.value - b.value;
  105.                 }
  106.                
  107.                 return b.index - a.index;
  108.             }
  109.         });
  110.        
  111.         int n = a.length;
  112.        
  113.         int[] lefts = new int[n], rights = new int[n];
  114.                
  115.         NavigableSet<Integer> indexes = new TreeSet<Integer>();
  116.         indexes.add(-1);
  117.         indexes.add(n);
  118.        
  119.         for (IntIndexPair pair : iip) {
  120.             int index = pair.index;
  121.            
  122.             int prevIndex = indexes.lower(index);
  123.             int nextIndex = indexes.higher(index);
  124.            
  125.             lefts[index] = prevIndex;
  126.             rights[index] = nextIndex;
  127.                        
  128.             indexes.add(index);
  129.         }
  130.        
  131.         final long NEGATIVE_INF = Long.MIN_VALUE / 3;
  132.        
  133.         long[][] dp = new long[k + 2][n + 1];
  134.        
  135.         for (long[] dp1 : dp) {
  136.             Arrays.fill(dp1, NEGATIVE_INF);
  137.         }
  138.        
  139.         dp[0][0] = 0;
  140.        
  141.         long answer = NEGATIVE_INF;
  142.        
  143.         ConvexHullTrick[] tricks = new ConvexHullTrick[k + 2];
  144.         for (int j = 0; j < tricks.length; ++j) {
  145.             tricks[j] = new ConvexHullTrick(n, dp[j][0]);
  146.         }
  147.        
  148.         for (int i = 0; i < n; ++i) {
  149.             int left = lefts[i];
  150.             int right = rights[i];
  151.            
  152.             long value = a[i];
  153.             long curSquare = (i - left) * value;
  154.            
  155.             for (int j = 1; j <= k + 1; ++j) {
  156.                 long curDp = dp[j][i + 1];
  157.                
  158.                 ConvexHullTrick trick = tricks[j - 1];
  159.                 trick.updateStack(value);
  160.                
  161.                 long best = trick.getBest(left);
  162.                
  163.                 if (best != NEGATIVE_INF) {
  164.                     curDp = Math.max(curDp, curSquare + best);
  165.                 }
  166.                
  167.                 answer = Math.max(answer,  curDp + (right - i - 1) * value);
  168.                
  169.                 dp[j][i + 1] = curDp;
  170.             }
  171.  
  172.             for (int j = 1; j <= k + 1; ++j) {
  173.                 if (dp[j][i + 1] != NEGATIVE_INF) {
  174.                     tricks[j].addLine(i, value, dp[j][i + 1] - value * i); 
  175.                 }
  176.                
  177.             }
  178.         }
  179.        
  180.         for (long[] dp1 : dp) {
  181.             for (long value : dp1) {
  182.                 answer = Math.max(answer, value);
  183.             }
  184.         }
  185.        
  186.         return answer;
  187.     }
RAW Paste Data