Guest User

ProblemE CF465

a guest
Feb 20th, 2018
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class ProblemE {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.        
  7.         String s=sc.next();
  8.         int P=sc.nextInt();
  9.         int M=sc.nextInt();
  10.        
  11.         Deque<Character> stack = new ArrayDeque<Character>();
  12.         Deque<Character> queue = new ArrayDeque<Character>();
  13.        
  14.         for (Character c:s.toCharArray()){
  15.             if ("0123456789".contains(c.toString())){
  16.                 queue.addLast(c);
  17.             }
  18.             else if (c=='('){
  19.                 stack.addLast(c);
  20.             }
  21.             else if (c==')'){
  22.                 Character pop=null;
  23.                 while (true){
  24.                     pop=stack.removeLast();
  25.                     if (pop=='(') break;
  26.                     queue.addLast(pop);
  27.                 }
  28.             }
  29.             else{
  30.                 stack.addLast(c);
  31.             }
  32.         }
  33.         while (!stack.isEmpty()){
  34.             queue.addLast(stack.removeLast());
  35.         }
  36.        
  37.         Deque<Node> nStack = new ArrayDeque<Node>();
  38.         while (!queue.isEmpty()){
  39.             Character c = queue.removeFirst();
  40.             if (c=='?'){
  41.                 Node r = nStack.removeLast();
  42.                 Node l = nStack.removeLast();
  43.                 nStack.addLast(new Node(l,r));
  44.             }
  45.             else{
  46.                 nStack.addLast(new Node(Integer.parseInt(c.toString())));
  47.             }
  48.         }
  49.        
  50.         if (P>100){
  51.             Node root = nStack.removeFirst();
  52.             postOrder(root);
  53.             System.out.println(root.maxUsingKM[M]);
  54.         }
  55.         else{
  56.             Node root = nStack.removeFirst();
  57.             postOrder(root);
  58.             System.out.println(root.maxUsingKP[P]);
  59.         }
  60.        
  61.     }
  62.    
  63.     static void postOrder(Node root){
  64.         if (root.left==null){
  65.             visit(root);
  66.         }
  67.         else{
  68.             postOrder(root.left);
  69.             postOrder(root.right);
  70.             visit(root);
  71.         }
  72.        
  73.     }
  74.    
  75.    
  76.     static void visit(Node root){
  77.        
  78.         if (root.type==nType.NUM){
  79.             root.maxUsingKP[0]=root.num;
  80.             root.minUsingKP[0]=root.num;
  81.             root.maxUsingKM[0]=root.num;
  82.             root.minUsingKM[0]=root.num;
  83.         }
  84.         else{
  85.             //ovisi koliko pluseva i minusa koristimo
  86.             for (int p=0;p<=100;p++){
  87.                 for (int left=0;left<p;left++){
  88.                     //stavimo plus
  89.                     root.maxUsingKP[p]=Math.max(root.maxUsingKP[p], root.left.maxUsingKP[left]+root.right.maxUsingKP[p-left-1]);
  90.                     root.minUsingKP[p]=Math.min(root.minUsingKP[p], root.left.minUsingKP[left]+root.right.minUsingKP[p-left-1]);
  91.                 }
  92.                 for (int left=0;left<=p;left++){
  93.                     //stavimo minus
  94.                     root.maxUsingKP[p]=Math.max(root.maxUsingKP[p], root.left.maxUsingKP[left]-root.right.minUsingKP[p-left]);
  95.                     root.minUsingKP[p]=Math.min(root.minUsingKP[p], root.left.minUsingKP[left]-root.right.maxUsingKP[p-left]);
  96.                 }
  97.             }
  98.             for (int p=0;p<=100;p++){
  99.                 for (int left=0;left<=p;left++){
  100.                     //stavimo plus
  101.                     root.maxUsingKM[p]=Math.max(root.maxUsingKM[p], root.left.maxUsingKM[left]+root.right.maxUsingKM[p-left]);
  102.                     root.minUsingKM[p]=Math.min(root.minUsingKM[p], root.left.minUsingKM[left]+root.right.minUsingKM[p-left]);
  103.                 }
  104.                 for (int left=0;left<p;left++){
  105.                     //stavimo minus
  106.                     root.maxUsingKM[p]=Math.max(root.maxUsingKM[p], root.left.maxUsingKM[left]-root.right.minUsingKM[p-left-1]);
  107.                     root.minUsingKM[p]=Math.min(root.minUsingKM[p], root.left.minUsingKM[left]-root.right.maxUsingKM[p-left-1]);
  108.                 }
  109.             }
  110.         }
  111.        
  112.     }
  113.    
  114.     static class Node{
  115.         nType type;
  116.         int num;
  117.         Node left;
  118.         Node right;
  119.        
  120.         int size;
  121.         int[] maxUsingKP=new int[101];
  122.         int[] minUsingKP=new int[101];
  123.         int[] maxUsingKM=new int[101];
  124.         int[] minUsingKM=new int[101];
  125.         {
  126.             Arrays.fill(maxUsingKP, -1_000_000_000);
  127.             Arrays.fill(minUsingKP, +1_000_000_000);
  128.             Arrays.fill(maxUsingKM, -1_000_000_000);
  129.             Arrays.fill(minUsingKM, +1_000_000_000);
  130.         }
  131.        
  132.         public Node(int num){
  133.             type=nType.NUM;
  134.             this.num=num;
  135.             this.size=0;
  136.         }
  137.         public Node(Node left, Node right){
  138.             type=nType.OP;
  139.             this.left=left;
  140.             this.right=right;
  141.             this.size=left.size+right.size+1;
  142.         }
  143.     }
  144.     enum nType{
  145.         NUM,OP
  146.     }
  147. }
RAW Paste Data