D. Little thief Shi

Codeforces

IDCF10073D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Shi realized that he was almost out of money, even renting Shitalian lands. Shi was walking on a street, while thinking of a way to recover his fortune. In his way, he passed by a jewelry store. The owner of the store was a Shitalian man suspected of committing minor crimes, as cutting bushes and stealing old bread. Shi hated people who cut bushes, so he decided to rob the store to take revenge and make some money. The store has n jewels, put in a row, one after another. Each jewel i can be sold in the black market for a value vi. Shi wants to steal as much as possible, but if he steals everything, the owner will notice, so if Shi steals the i-th jewel, he can't steal the i - 1-th, i - 2-th, i + 1-th and i + 2-th jewels. Using the best strategy possible, calculate the sum of the jewels values that Shi can obtain. The input begins with an integer n (1 ≤ n ≤ 106), indicating the number of jewels in the store. The next line contains n integers. The i-th integer vi (1 ≤ vi ≤ 103) is the value of the i-th jewel. Output the maximum value that Shi can get. ## Input The input begins with an integer n (1 ≤ n ≤ 106), indicating the number of jewels in the store. The next line contains n integers. The i-th integer vi (1 ≤ vi ≤ 103) is the value of the i-th jewel. ## Output Output the maximum value that Shi can get. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of vertices. Let $ d = (d_1, d_2, \dots, d_n) \in \mathbb{Z}_{\geq 0}^n $ be the degree sequence of the vertices. **Constraints** 1. $ 1 \leq n \leq 200000 $ 2. $ d_i \geq 0 $ for all $ i \in \{1, \dots, n\} $ 3. The sum $ \sum_{i=1}^n d_i $ must be even (necessary for any graph). 4. For a tree: $ \sum_{i=1}^n d_i = 2(n - 1) $ 5. Each $ d_i \geq 1 $ (since a tree with $ n \geq 2 $ has no isolated vertices; if $ n = 1 $, then $ d_1 = 0 $). **Objective** Construct a tree on $ n $ vertices with degree sequence $ d $, or output $-1$ if no such tree exists. If a tree exists, output $ n - 1 $ edges (pairs of vertex indices) such that the resulting graph is a tree with the given degrees.

API Response (JSON)

{
  "problem": {
    "name": "D. Little thief Shi",
    "description": {
      "content": "Shi realized that he was almost out of money, even renting Shitalian lands. Shi was walking on a street, while thinking of a way to recover his fortune. In his way, he passed by a jewelry store. The o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10073D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Shi realized that he was almost out of money, even renting Shitalian lands. Shi was walking on a street, while thinking of a way to recover his fortune. In his way, he passed by a jewelry store. The o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices.  \nLet $ d = (d_1, d_2, \\dots, d_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be the degree sequence of the vertices.\n\n**Constraints**  \n1. $ 1 \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments