← CSES Better

Rectangle

ZCO · 2015 · Zonal Computing Olympiad · ZCO15004

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

geometry · sweep-line · optimization

The organizer’s problem statement is available at the official source link.

histogram rectangle

Each point caps the rectangle height to its left

For a fixed horizontal span, the rectangle’s height is limited by the lowest point inside that span.

State table
SpanLimiting heightArea
[L,R]min y inside span(R-L) * height
  1. 1

    Sweep point barriers

    Sort points by horizontal coordinate.
  2. 2

    Choose span and height

    Sweep candidate left/right boundaries while maintaining the lowest point that would enter the interior.
  3. 3

    Maximize area

    Compare each feasible width-times-height area, allowing boundary points.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.