Advertisement
Nevada112

CODE 101

May 1st, 2021
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.38 KB | None | 0 0
  1. import java.io.*;
  2. import java.lang.*;
  3. import java.util.*;
  4. class a
  5. {
  6. static class FastScanner {
  7. InputStreamReader is;
  8. BufferedReader br;
  9. StringTokenizer st;
  10. public FastScanner() {
  11. is = new InputStreamReader(System.in);
  12. br = new BufferedReader(is);
  13. }
  14. String next() throws Exception {
  15. while (st == null || !st.hasMoreElements())
  16. st = new StringTokenizer(br.readLine());
  17. return st.nextToken();
  18. }
  19. int nextInt() throws Exception {
  20. return Integer.parseInt(next());
  21. }
  22. long nextLong() throws Exception {
  23. return Long.parseLong(next());
  24. }
  25. int[] readArray(int num) throws Exception {
  26. int arr[]=new int[num];
  27. for(int i=0;i<num;i++)
  28. arr[i]=nextInt();
  29. return arr;
  30. }
  31. String nextLine() throws Exception {
  32. return br.readLine();
  33. }
  34. }
  35.  public static boolean power_of_two(int a)
  36. {
  37.   if((a&(a-1))==0)
  38. {
  39.  return true;
  40. }
  41. return false;
  42. }
  43.  
  44.  
  45. /////////////  M A I N    C O D E   S T A R T S      F R O M        H E R E   \\\\\\\\\\\\\\\
  46.  
  47.  
  48.  
  49. public static void main(String args[]) throws java.lang.Exception
  50. {
  51. FastScanner sc=new FastScanner();
  52.     int t=sc.nextInt();
  53.     while(t-->0)
  54.     {
  55.         int n=sc.nextInt();                // NO OF WEIGHTS
  56.                  
  57.         long w=sc.nextLong();              // WEIGHT TO BE LIFTED
  58.  
  59.         long wr=sc.nextLong();             // WEIGHT OF THE ROD
  60.        
  61.        
  62.       long ar[]=new long[n];
  63.       for(int i=0;i<n;i++)
  64.       {
  65.           ar[i]=sc.nextLong();
  66.       }
  67.       if(wr>=w)
  68.       {
  69.           System.out.println("YES");
  70.           continue;
  71.       }
  72.  
  73.  
  74. if((w-wr)%2!=0)                         // IF THE WEIGHT REQUIRED APART FROM RODS WEIGHT IS ODD THEN WE
  75.                                         // CAN DEVIDE IT EQUALLY TO BOTH THE SIDES
  76. {
  77.     System.out.println("NO");
  78.     continue;
  79. }
  80.  
  81. Arrays.sort(ar);                  // SORT THE ARRAY FOR GIVNG EQUAL OPPERTUNITY OF WEIGHTS TO EACH SIDE
  82.  
  83. Stack<Long> st1=new Stack<>();      // FOR CHECK THE SYMETRICITY OF SIDE 1 TO SIDE 2
  84. Stack<Long> st2=new Stack<>();      // // FOR CHECK THE SYMETRICITY OF SIDE 2 TO SIDE 1
  85.  
  86.  
  87. long req=(w-wr)/2;            // WEIGHT TO BE REQUIRED
  88. long sum1=0;
  89. long sum2=0;
  90.  
  91. for(int i=0;i<n;i++)
  92. {
  93.     if(sum1==req && sum2==req)           // IF THE REQ  SUM IS ACHIVED THEN COME OUT OF THE LOOP
  94.     {
  95.         break;
  96.     }
  97.  
  98.  
  99.     if(sum1<=sum2)                       // WE ARE DISTRIBUTING LIKE , THE SIDE WHICH HAVE LESS WEIGHTS
  100.                                          // CURRENTLY WILL GET THE CHANCE TO PUT THE WEIGHT TO ITS SIDE
  101.     {
  102.  
  103.  
  104. if(req-sum1>=ar[i])                      // WEIGHT WE ARE  PUTTING IS  ELIGIBL OR NOT  TO BE IN THE SIDE1
  105. {
  106.     st1.push(ar[i]);
  107.     sum1+=ar[i];
  108. }
  109.  
  110. else if(ar[i]>req-sum1)
  111. {
  112.     while(st1.size()>0 && ar[i]+sum1>req)
  113.     {
  114.         sum1-=st1.peek();
  115.         st1.pop();
  116.     }
  117.     if(sum1+ar[i]<=req)
  118.     {
  119.         sum1+=ar[i];
  120.         st1.push(ar[i]);
  121.     }
  122. }
  123.     }
  124.  
  125.  
  126.  
  127.  
  128.     if(sum2<sum1)                  // CHECKING FOR THE SIDE 2
  129.     {
  130. if(req-sum2>=ar[i])
  131. {
  132.     st2.push(ar[i]);
  133.     sum2+=ar[i];
  134. }
  135. else if(ar[i]>req-sum2)
  136. {
  137.     while(st2.size()>0 && ar[i]+sum2>req)
  138.     {
  139.         sum2-=st2.peek();
  140.         st2.pop();
  141.     }
  142.     if(sum2+ar[i]<=req)
  143.     {
  144.         sum2+=ar[i];
  145.         st2.push(ar[i]);
  146.     }
  147. }
  148.     }
  149. }
  150.  
  151.  
  152.  
  153.  
  154.  
  155. if(sum1==req && sum2==req)
  156. {
  157.     System.out.println("YES");
  158. }                      
  159. else{
  160.     System.out.println("NO");
  161. }
  162. }
  163. }
  164. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement