-->

10/18/20

Adding Squares Codechef October Long challenge Problem Code

 Adding Squares  Codechef October Long challenge Problem Code-

problem Statement-

There are N different vertical lines on the plane, i-th of which is defined by the equation x=ai (0aiW) and M different horizontal lines, i-th of which is defined by the equation y=bi (0biH). You must add one line of the form y=k (0kHkbi for every 1iM) to the plane. What is the maximum possible number of squares with different areas you can obtain on the plane? (Squares can have other lines passing through them)

Input:

  • First line will contain 4 integers WHNM
  • Second line will contain N different integers a1,a2,...,aN
  • Third line will contain M different integers b1,b2,...,bM

Output:

Output the maximal possible number of squares with different area on the plane after adding a new line.

Constraints

  • 1W,H,N,M105
  • NW+1
  • MH
  • 0aiW for every 1iN
  • 0biH for every 1iM

Subtasks

  • 50 points : 1H,W1000
  • 50 points : Original constraints

Sample Input:

10 10 3 3
3 6 8
1 6 10

Sample Output:

3

Explanation:

You can get 3 different squares if you add a line y=4. The three squares are:

  • Square with top-left corner at (6, 6) and bottom-right corner at (8, 4) with an area of 4.
  • Square with top-left corner at (3, 4) and bottom-right corner at (6, 1) with an area of 9.
  • Square with top-left corner at (3, 6) and bottom-right corner at (8, 1) with an area of 25.
codechef long challenge



Solution -


Learn Bitset-
Follow the Link below for the bitset data structure and then follow my code.

C++ bitset and its application - GeeksforGeeks

www.geeksforgeeks.org › c-bitset-and-its-application


bitset - C++ Reference - Cplusplus.com

www.cplusplus.com › Reference › <bitset>



Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.