Tap here to switch tabs
Problem
Submissions

Problem: Maximum Cake Area After Horizontal and Vertical Cuts

Maximum Cake Area After Horizontal and Vertical Cuts gives a rectangular cake's dimensions and horizontal and vertical cut positions, asking for the largest piece area modulo a large prime.

Statement

You are given a rectangular cake of dimensions h ×\times w and two integer arrays horizontalCuts and verticalCuts where:

  • horizontalCuts[i] is the distance from the top of the rectangular cake to the ithi^{ {th}} horizontal cut.

  • verticalCuts[j] is the distance from the left of the rectangular cake to the jthj^{ {th}} vertical cut.

Return the maximum area of a piece of cake after you make all the horizontal and vertical cuts.

Note: Since the answer can be large, return it modulo 109+710^9 + 7.

Constraints:

  • 2≤2 \leq h, w ≤109\leq 10^9

  • 1≤1 \leq horizontalCuts.length ≤min⁡(\leq \min( h −1,105)- 1, 10^5)

  • 1≤1 \leq verticalCuts.length ≤min⁡(\leq \min( w −1,105)- 1, 10^5)

  • 1≤1 \leq horizontalCuts[i] << h

  • 1≤1 \leq verticalCuts[i] << w

  • All the elements in horizontalCuts are distinct.

  • All the elements in verticalCuts are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Cake Area After Horizontal and Vertical Cuts

Maximum Cake Area After Horizontal and Vertical Cuts gives a rectangular cake's dimensions and horizontal and vertical cut positions, asking for the largest piece area modulo a large prime.

Statement

You are given a rectangular cake of dimensions h ×\times w and two integer arrays horizontalCuts and verticalCuts where:

  • horizontalCuts[i] is the distance from the top of the rectangular cake to the ithi^{ {th}} horizontal cut.

  • verticalCuts[j] is the distance from the left of the rectangular cake to the jthj^{ {th}} vertical cut.

Return the maximum area of a piece of cake after you make all the horizontal and vertical cuts.

Note: Since the answer can be large, return it modulo 109+710^9 + 7.

Constraints:

  • 2≤2 \leq h, w ≤109\leq 10^9

  • 1≤1 \leq horizontalCuts.length ≤min⁡(\leq \min( h −1,105)- 1, 10^5)

  • 1≤1 \leq verticalCuts.length ≤min⁡(\leq \min( w −1,105)- 1, 10^5)

  • 1≤1 \leq horizontalCuts[i] << h

  • 1≤1 \leq verticalCuts[i] << w

  • All the elements in horizontalCuts are distinct.

  • All the elements in verticalCuts are distinct.