E. Hanoi Factory

Codeforces

IDCF777E

Time1000ms

Memory256MB

Difficulty—

brute forcedata structuresdpgreedysortings

English · Original

Chinese · Translation

Formal · Original

Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings. There are _n_ rings in factory's stock. The _i_\-th ring has inner radius _a__i_, outer radius _b__i_ and height _h__i_. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied: * Outer radiuses form a non-increasing sequence, i.e. one can put the _j_\-th ring on the _i_\-th ring only if _b__j_ ≤ _b__i_. * Rings should not fall one into the the other. That means one can place ring _j_ on the ring _i_ only if _b__j_ > _a__i_. * The total height of all rings used should be maximum possible. ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — the number of rings in factory's stock. The _i_\-th of the next _n_ lines contains three integers _a__i_, _b__i_ and _h__i_ (1 ≤ _a__i_, _b__i_, _h__i_ ≤ 109, _b__i_ > _a__i_) — inner radius, outer radius and the height of the _i_\-th ring respectively. ## Output Print one integer — the maximum height of the tower that can be obtained. [samples] ## Note In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1. In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

当然，你一定听说过著名的汉诺塔问题，但你是否知道，有一个专门生产该游戏圆环的特殊工厂？从前，古埃及的统治者命令汉诺工厂的工人建造尽可能高的塔。他们并不准备接受如此奇怪的命令，因此不得不使用已生产的圆环来建造这座新塔。工厂库存中有 #cf_span[n] 个圆环。第 #cf_span[i] 个圆环的内半径为 #cf_span[ai]，外半径为 #cf_span[bi]，高度为 #cf_span[hi]。目标是从中选择一个子集，并将它们按如下条件排列：输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 工厂库存中的圆环数量。接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含三个整数 #cf_span[ai]、#cf_span[bi] 和 #cf_span[hi] (#cf_span[1 ≤ ai, bi, hi ≤ 10^9]，#cf_span[bi > ai]) —— 分别表示第 #cf_span[i] 个圆环的内半径、外半径和高度。请输出一个整数 —— 可以获得的塔的最大高度。在第一个测试用例中，最优解是取所有圆环，并按 #cf_span[3]、#cf_span[2]、#cf_span[1] 的顺序叠放。在第二个测试用例中，可以将圆环 #cf_span[3] 放在圆环 #cf_span[4] 上，得到高度为 #cf_span[3] 的塔；或将圆环 #cf_span[1] 放在圆环 #cf_span[2] 上，得到高度为 #cf_span[4] 的塔。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 工厂库存中的圆环数量。第 #cf_span[i] 行接下来的 #cf_span[n] 行包含三个整数 #cf_span[ai]、#cf_span[bi] 和 #cf_span[hi] (#cf_span[1 ≤ ai, bi, hi ≤ 10^9]，#cf_span[bi > ai]) —— 分别表示第 #cf_span[i] 个圆环的内半径、外半径和高度。 ## Output 请输出一个整数 —— 可以获得的塔的最大高度。 [samples] ## Note 在第一个测试用例中，最优解是取所有圆环，并按 #cf_span[3]、#cf_span[2]、#cf_span[1] 的顺序叠放。在第二个测试用例中，可以将圆环 #cf_span[3] 放在圆环 #cf_span[4] 上，得到高度为 #cf_span[3] 的塔；或将圆环 #cf_span[1] 放在圆环 #cf_span[2] 上，得到高度为 #cf_span[4] 的塔。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of rings. For each ring $ i \in \{1, \dots, n\} $, define: - $ a_i \in \mathbb{Z}^+ $: inner radius, - $ b_i \in \mathbb{Z}^+ $: outer radius, with $ b_i > a_i $, - $ h_i \in \mathbb{Z}^+ $: height. A tower is a sequence of rings $ (i_1, i_2, \dots, i_k) $ such that for all $ j \in \{1, \dots, k-1\} $, the outer radius of ring $ i_j $ is **greater than** the inner radius of ring $ i_{j+1} $: $$ b_{i_j} > a_{i_{j+1}}. $$ **Constraints** 1. $ 1 \le n \le 100{,}000 $ 2. $ 1 \le a_i, b_i, h_i \le 10^9 $ 3. $ b_i > a_i $ for all $ i $ **Objective** Maximize the total height of a valid tower: $$ \max \sum_{j=1}^k h_{i_j} $$ over all valid sequences $ (i_1, \dots, i_k) $ satisfying the stacking condition.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Hanoi Factory",
    "description": {
      "content": "Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Eg",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF777E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Eg...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "当然，你一定听说过著名的汉诺塔问题，但你是否知道，有一个专门生产该游戏圆环的特殊工厂？从前，古埃及的统治者命令汉诺工厂的工人建造尽可能高的塔。他们并不准备接受如此奇怪的命令，因此不得不使用已生产的圆环来建造这座新塔。\n\n工厂库存中有 #cf_span[n] 个圆环。第 #cf_span[i] 个圆环的内半径为 #cf_span[ai]，外半径为 #cf_span[bi]，高度为 #cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of rings.  \nFor each ring $ i \\in \\{1, \\dots, n\\} $, define:  \n- $ a_i \\in \\mathbb{Z}^+ $: inner radius,  \n- $ b_i \\in \\mathbb{Z}^+ $: outer ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments