Advertisement
Nevada112

CODE 101

May 1st, 2021
275
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.37 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'T 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                                     // CURRENTLY WILL GET THE CHANCE TO PUT THE WEIGHT TO ITS SIDE
  100.     {
  101. if(req-sum1>=ar[i])                      // WEIGHT WE ARE  PUTTING IS  ELIGIBL OR NOT  TO BE IN THE SIDE1
  102. {
  103.     st1.push(ar[i]);
  104.     sum1+=ar[i];
  105. }
  106.  
  107. else if(ar[i]>req-sum1)
  108. {
  109.     while(st1.size()>0 && ar[i]+sum1>req)
  110.     {
  111.         sum1-=st1.peek();
  112.         st1.pop();
  113.     }
  114.     if(sum1+ar[i]<=req)
  115.     {
  116.         sum1+=ar[i];
  117.         st1.push(ar[i]);
  118.     }
  119. }
  120.     }
  121.  
  122.  
  123.  
  124.  
  125.     if(sum2<sum1)                  // CHECKING FOR THE SIDE 2
  126.     {
  127. if(req-sum2>=ar[i])
  128. {
  129.     st2.push(ar[i]);
  130.     sum2+=ar[i];
  131. }
  132. else if(ar[i]>req-sum2)
  133. {
  134.     while(st2.size()>0 && ar[i]+sum2>req)
  135.     {
  136.         sum2-=st2.peek();
  137.         st2.pop();
  138.     }
  139.     if(sum2+ar[i]<=req)
  140.     {
  141.         sum2+=ar[i];
  142.         st2.push(ar[i]);
  143.     }
  144. }
  145.     }
  146. }
  147.  
  148.  
  149.  
  150.  
  151.  
  152. if(sum1==req && sum2==req)
  153. {
  154.     System.out.println("YES");
  155. }                      
  156. else{
  157.     System.out.println("NO");
  158. }
  159. }
  160. }
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement