D. Roads (A)

Codeforces

IDCF10140D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The length of the ith road is wi. Let dist(u, v) be the length of the shortest path that goes between city u and city v. Your task is to find the total sum of dist(u, v) for all pairs (u, v) (1 ≤ u < v ≤ N). The first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities. The second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road. Print the required sum on a single line. ## Input The first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities.The second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road. ## Output Print the required sum on a single line. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ with $ 3 \leq N \leq 2 \times 10^5 $. Let $ w = (w_1, w_2, \dots, w_N) $ be a sequence of positive integers representing road lengths, where $ w_i $ is the length of the road between city $ i $ and city $ i+1 $ for $ 1 \leq i < N $, and $ w_N $ is the length of the road between city $ N $ and city $ 1 $. The graph is a cycle $ C_N $ with edge weights $ w_i $. Let $ \text{dist}(u, v) $ denote the shortest path distance between cities $ u $ and $ v $ along the cycle. **Constraints** $ 1 \leq w_i \leq 1000 $ for all $ i \in \{1, \dots, N\} $ **Objective** Compute the sum: $$ \sum_{1 \leq u < v \leq N} \text{dist}(u, v) $$ where $ \text{dist}(u, v) = \min\left( \sum_{i=u}^{v-1} w_i, \sum_{i=v}^{u-1} w_i \right) $ (with indices taken modulo $ N $, and the sum over a circular segment).

API Response (JSON)

{
  "problem": {
    "name": "D. Roads (A)",
    "description": {
      "content": "There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10140D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 3 \\leq N \\leq 2 \\times 10^5 $.  \nLet $ w = (w_1, w_2, \\dots, w_N) $ be a sequence of positive integers representing road lengths, where $ w_i $ is the...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments