F. Sum then Multiply

Codeforces

IDCF10219F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an array of n positive integers. You want to divide the array into one or more parts, where each part is a subarray of the original array. Every integer must be included in exactly one part. After that, you will get the sum of each part, then multiply all the sums together. For example, the array [8, 1, 1, 3] can be divided into parts [8], [1, 1], and [3], with sums 8, 2, and 3, respectively, giving a product of 48. Note that each part consists of consecutive elements of the array. Divide the given array in a way that maximizes the final product. The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the size of the array. The second line of input contains n integers ai (1 ≤ ai ≤ 109), where ai is the ith integer in the array. Print exactly one line; the line must contain the input succession a1, a2, ... an divided into parts such that the product of the sums of each part is maximized. Use the slash character ('/') to separate the parts. Separate numbers and slashes with a single space. If there are multiple solutions, print any of them. ## Input The first line of input contains a single integer n (1 ≤ n ≤ 3 × 105), the size of the array.The second line of input contains n integers ai (1 ≤ ai ≤ 109), where ai is the ith integer in the array. ## Output Print exactly one line; the line must contain the input succession a1, a2, ... an divided into parts such that the product of the sums of each part is maximized. Use the slash character ('/') to separate the parts. Separate numbers and slashes with a single space.If there are multiple solutions, print any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, n\} $. **Constraints** 1. $ 1 \leq n \leq 3 \times 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Partition $ A $ into $ k \geq 1 $ contiguous non-empty subarrays $ A_1, A_2, \dots, A_k $, such that: - $ \bigcup_{j=1}^k A_j = A $, and $ A_j \cap A_{j'} = \emptyset $ for $ j \neq j' $, - Each $ A_j $ is a contiguous subarray of $ A $, - The product $ P = \prod_{j=1}^k \left( \sum_{a_i \in A_j} a_i \right) $ is maximized. **Output** A string representation of the partition, where adjacent elements of $ A $ are separated by spaces, and subarrays are separated by " / " (space before and after slash).

API Response (JSON)

{
  "problem": {
    "name": "F. Sum then Multiply",
    "description": {
      "content": "You are given an array of n positive integers. You want to divide the array into one or more parts, where each part is a subarray of the original array. Every integer must be included in exactly one p",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10219F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array of n positive integers. You want to divide the array into one or more parts, where each part is a subarray of the original array. Every integer must be included in exactly one p...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in \\mathbb{Z}^+ $ for all $ i \\in \\{1, \\d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments