A. Accordion Artist And Orz Pandas

Codeforces

IDCF10287A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Chuan _the Country Builder_ is a famous accordion artist. Now he wants to put a "Make Accordion Great Again" advertisment, in order to get some advantage over his enemy Bai _the Sleeper_. There are $n$ buildings on the 114514th Avenue, the Old York city. The premium alongside the 114514th Avenue is very high so there is no margin between two adjacent buildings. The front view of the $i$-th building can be approximated with a rectangle with height $h_i$ and width $w_i$. Chuan wants his advertisment to be a _great_ one. More specifically, it must be a rectangle with the height perpendicular to the height of the front view of each building, and the entire advertisment must fit in the union of the front views of the buildings. An Orz Panda company has made a contract to build the advertisment for Chuan. The company wants the area of the advertisment to be as large as possible, so they can get more money from Chuan. Please calculate the maximum possible area of all _great_ advertisments. There is only one test case in the input file. The first line contains an integer $n$, the number of the buildings. The $i$-th of the following $n$ lines contains two integers $h_i$, $w_i$, the height and weight of the $i$-th building. It's guaranteed that $1 <= n <= 10^5$, and $1 <= h_i, w_i <= 10^5$. Output one line containing the maximum area. The _great_ advertisment with maximum area is illustrated in the following figure. The grey area is the front view of the buildings. There is some margin deliberately added around the advertisment, to make the figure clear. ## Input There is only one test case in the input file.The first line contains an integer $n$, the number of the buildings.The $i$-th of the following $n$ lines contains two integers $h_i$, $w_i$, the height and weight of the $i$-th building.It's guaranteed that $1 <= n <= 10^5$, and $1 <= h_i, w_i <= 10^5$. ## Output Output one line containing the maximum area. [samples] ## Note The _great_ advertisment with maximum area is illustrated in the following figure. The grey area is the front view of the buildings. There is some margin deliberately added around the advertisment, to make the figure clear.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of students. Let $ C \in \mathbb{Z}^+ $ be the maximum allowed IQ difference per team. Let $ C = (c_1, c_2, \dots, c_n) $ be a sequence of non-negative integers representing the IQs of the students. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ 1 \leq C \leq 50 $ 3. $ 0 \leq c_i \leq 200 $ for all $ i \in \{1, \dots, n\} $ **Objective** Partition as many students as possible into disjoint teams of exactly three students each, such that for every team with IQs $ \{a, b, c\} $, the condition $$ \max(a, b, c) - \min(a, b, c) \leq C $$ is satisfied. Maximize the number of such teams.

API Response (JSON)

{
  "problem": {
    "name": "A. Accordion Artist And Orz Pandas",
    "description": {
      "content": "Chuan _the Country Builder_ is a famous accordion artist. Now he wants to put a \"Make Accordion Great Again\" advertisment, in order to get some advantage over his enemy Bai _the Sleeper_. There are $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10287A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Chuan _the Country Builder_ is a famous accordion artist. Now he wants to put a \"Make Accordion Great Again\" advertisment, in order to get some advantage over his enemy Bai _the Sleeper_.\n\nThere are $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of students.  \nLet $ C \\in \\mathbb{Z}^+ $ be the maximum allowed IQ difference per team.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be a sequence o...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments