Dinocoder's blog

By Dinocoder, history, 5 months ago, In English

There are N tutors who have been assigned to teach N students in a mathematics class. Every tutor's and student's knowledge about mathematics can be defined by a pair of values: A (Algebra) and G (Geometry)All the A values are pairwise distinct, and similarly, all the G values are pairwise distinct.

A tutor t can teach a student s if and only if G_{t} > G_{s} and A_{t} > A_{s}. Find the maximum number of tutor-student pairings which follow the above condition.

Input Format

The first line contains a single integer N (1 <= N <= 2 * 10 ^ 5) denoting the number of students and the number of tutors both.

The next N lines describe the students and contain two integers A (1 <= A <= 10 ^ 9) and G(1 <= G <= 10 ^ 9) per line denoting the algebra and the geometry skill values for each student.

The next N lines describe the tutors and contain two integers A (1 <= A <= 10 ^ 9) and G(1 <= G <= 10 ^ 9) per line, denoting the algebra and the geometry skill values for each tutor

Output Format

Output maximum number of tutor-student pairings satisfying the condition

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By Dinocoder, history, 5 months ago, In English

You are given an integer N denoting the number of seats in a cinema hall numbered from 1 to N. There are M groups where B[i] denotes the number of persons in the ith group. The persons from the same group want to sit together. A[i] denotes the cost of the ith seat ticket. You have to help the cinema hall owner make the maximum possible profit by assigning the seats to the groups optimally.

Calculate the maximum profit the cinema hall owner can make through an optimal seating arrangement.

Parameters description

• N: Represents the number of seats in the cinema hall

• M: Represents the number of groups visiting the cinema hall

• A: Represents the array A, where A[i] represents the cost of the ith seat ticket

B: Represents the array B, where B[i] represents the number of persons in the ith group

Input format

The first line contains a positive integer N denoting the size of the array A. The second line contains a positive integer M denoting the size of the array B.

The third line contains N positive space-separated integers denoting elements of the array A.

The fourth line contains M positive space-separated integers denoting elements of the array B.

Output format

Print a single integer denoting the maximum profit the cinema hall owner can make through an optimal seating arrangement.

Constraints

1 <= N <= 5 * 10 ^ 2

1 <= M <= 13

1 <= A_{i} <= 10 ^ 9

1 <= B_{i} <= N

B_{1} + B_{2} + B_{3} +.......+B M <=N

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it