E. Lines Game

Codeforces

IDCF10123E

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0, i) and (1, pi), where the numbers p1, p2, ..., pN are a permutation of numbers from 1 to N. Your are also given N positive integers v1, v2, ..., vN. On each step, you can select any segment i which is not removed yet, pay vi dollars, and then remove the i-th segment and all segments intersecting with it. Note that you MUST remove all segments which intersect with i-th segment. The purpose of this game is to remove all segments while spending the minimum possible sum of dollars. Please answer how much you need to spend when you play the game with best strategy. The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN. Output only one number indicating the minimum possible sum of dollars required to remove all segments. ## Input The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1, p2, ..., pN. The third line consists of N integer v1, v2, ..., vN. 1 ≤ N ≤ 105 is a permutation of 1, 2, ..., N 1 ≤ vi ≤ 2 × 104 ## Output Output only one number indicating the minimum possible sum of dollars required to remove all segments. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $. Let $ \mathbf{p} = (p_1, p_2, \dots, p_N) $ be a permutation of $ \{1, 2, \dots, N\} $. Let $ \mathbf{v} = (v_1, v_2, \dots, v_N) \in \mathbb{R}^N_{>0} $. For each $ i \in \{1, \dots, N\} $, define segment $ s_i $ as the line segment connecting $ (0, i) $ and $ (1, p_i) $. **Constraints** Segments $ s_i $ and $ s_j $ (with $ i \ne j $) intersect if and only if $ (i - j)(p_i - p_j) < 0 $. **Objective** Find the minimum total cost to remove all segments, where selecting segment $ i $ costs $ v_i $ and removes $ i $ and all segments intersecting $ s_i $. Formally, find: $$ \min_{\text{covering sets } C} \sum_{i \in C} v_i $$ where $ C \subseteq \{1, \dots, N\} $ is a set such that every segment $ j \in \{1, \dots, N\} $ is either in $ C $ or intersects some segment in $ C $.

API Response (JSON)

{
  "problem": {
    "name": "E. Lines Game",
    "description": {
      "content": "Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0, i) and (1, pi), where the numbers p1, p2, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10123E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0, i) and (1, pi), where the numbers p1, p2, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $.  \nLet $ \\mathbf{p} = (p_1, p_2, \\dots, p_N) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \nLet $ \\mathbf{v} = (v_1, v_2, \\dots, v_N) \\in \\mathbb{R}^N_{>0...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments