Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.lang.*;
- import java.util.*;
- class a
- {
- static class FastScanner {
- InputStreamReader is;
- BufferedReader br;
- StringTokenizer st;
- public FastScanner() {
- is = new InputStreamReader(System.in);
- br = new BufferedReader(is);
- }
- String next() throws Exception {
- while (st == null || !st.hasMoreElements())
- st = new StringTokenizer(br.readLine());
- return st.nextToken();
- }
- int nextInt() throws Exception {
- return Integer.parseInt(next());
- }
- long nextLong() throws Exception {
- return Long.parseLong(next());
- }
- int[] readArray(int num) throws Exception {
- int arr[]=new int[num];
- for(int i=0;i<num;i++)
- arr[i]=nextInt();
- return arr;
- }
- String nextLine() throws Exception {
- return br.readLine();
- }
- }
- public static boolean power_of_two(int a)
- {
- if((a&(a-1))==0)
- {
- return true;
- }
- return false;
- }
- ///////////// M A I N C O D E S T A R T S F R O M H E R E \\\\\\\\\\\\\\\
- public static void main(String args[]) throws java.lang.Exception
- {
- FastScanner sc=new FastScanner();
- int t=sc.nextInt();
- while(t-->0)
- {
- int n=sc.nextInt(); // NO OF WEIGHTS
- long w=sc.nextLong(); // WEIGHT TO BE LIFTED
- long wr=sc.nextLong(); // WEIGHT OF THE ROD
- long ar[]=new long[n];
- for(int i=0;i<n;i++)
- {
- ar[i]=sc.nextLong();
- }
- if(wr>=w)
- {
- System.out.println("YES");
- continue;
- }
- if((w-wr)%2!=0) // IF THE WEIGHT REQUIRED APART FROM RODS WEIGHT IS ODD THEN WE
- // CAN'T DEVIDE IT EQUALLY TO BOTH THE SIDES
- {
- System.out.println("NO");
- continue;
- }
- Arrays.sort(ar); // SORT THE ARRAY FOR GIVNG EQUAL OPPERTUNITY OF WEIGHTS TO EACH SIDE
- Stack<Long> st1=new Stack<>(); // FOR CHECK THE SYMETRICITY OF SIDE 1 TO SIDE 2
- Stack<Long> st2=new Stack<>(); // // FOR CHECK THE SYMETRICITY OF SIDE 2 TO SIDE 1
- long req=(w-wr)/2; // WEIGHT TO BE REQUIRED
- long sum1=0;
- long sum2=0;
- for(int i=0;i<n;i++)
- {
- if(sum1==req && sum2==req) // IF THE REQ SUM IS ACHIVED THEN COME OUT OF THE LOOP
- {
- break;
- }
- 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
- {
- if(req-sum1>=ar[i]) // WEIGHT WE ARE PUTTING IS ELIGIBL OR NOT TO BE IN THE SIDE1
- {
- st1.push(ar[i]);
- sum1+=ar[i];
- }
- else if(ar[i]>req-sum1)
- {
- while(st1.size()>0 && ar[i]+sum1>req)
- {
- sum1-=st1.peek();
- st1.pop();
- }
- if(sum1+ar[i]<=req)
- {
- sum1+=ar[i];
- st1.push(ar[i]);
- }
- }
- }
- if(sum2<sum1) // CHECKING FOR THE SIDE 2
- {
- if(req-sum2>=ar[i])
- {
- st2.push(ar[i]);
- sum2+=ar[i];
- }
- else if(ar[i]>req-sum2)
- {
- while(st2.size()>0 && ar[i]+sum2>req)
- {
- sum2-=st2.peek();
- st2.pop();
- }
- if(sum2+ar[i]<=req)
- {
- sum2+=ar[i];
- st2.push(ar[i]);
- }
- }
- }
- }
- if(sum1==req && sum2==req)
- {
- System.out.println("YES");
- }
- else{
- System.out.println("NO");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement