E. Exciting Acts

Codeforces

IDCF10236E

Time1000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Aram has decided to make an autobiographical play about his life. His script has $N$ scenes with varying levels of excitement. For example, the scene of him studying for his first year exam was not very exciting, so Aram might rate it with an excitement level of $1$. On the other hand, the scene with Aram at ICPC World Finals was very exciting, so its excitement level might be $1 thin 000$. Aram needs to split the play into $K$ acts. He knows that each act will only be remembered by the most exciting scene in it, so the excitement level of each act is the excitement level of the most exciting scene in the act. Since the scenes are chronologically ordered, each act must consist of a non-empty contiguous set of scenes. Every scene must appear in exactly one act. The excitement of the play is the sum of excitements of the acts. Help Aram make the most exciting play! The first line contains two integers $N$ and $K$ ($1 <= K <= N <= 2 thin 000$), the number of scenes and acts, respectively. The second line contains $N$ space-separated integers. The $i$'th integer is $a_i$ ($1 <= a_i <= 1 thin 000$), the excitement level of the $i$th scene. Output a single integer, the maximum total excitement of the whole play. ## Input The first line contains two integers $N$ and $K$ ($1 <= K <= N <= 2 thin 000$), the number of scenes and acts, respectively.The second line contains $N$ space-separated integers. The $i$'th integer is $a_i$ ($1 <= a_i <= 1 thin 000$), the excitement level of the $i$th scene. ## Output Output a single integer, the maximum total excitement of the whole play. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be an even integer, $ 2 \leq N \leq 74 $. Let $ X = (x_0, x_1, \dots, x_{N-1}) $ be a sequence of non-negative integers, $ 0 \leq x_i \leq 1000 $. Let $ \mathcal{P} $ be the set of all perfect matchings (pairings) of the $ N $ stones, where each pairing is an unordered set of $ N/2 $ unordered pairs $ \{i,j\} $, partitioning $ \{0,1,\dots,N-1\} $. For a pairing $ P \in \mathcal{P} $, define the cost: $$ \text{cost}(P) = \sum_{\{i,j\} \in P} (x_i \oplus x_j) $$ where $ \oplus $ denotes bitwise XOR. **Constraints** 1. $ N $ is even, $ 2 \leq N \leq 74 $ 2. $ x_i \in \mathbb{Z} $, $ 0 \leq x_i \leq 1000 $ for all $ i \in \{0,1,\dots,N-1\} $ **Objective** Find: - $ S_{\min} = \min_{P \in \mathcal{P}} \text{cost}(P) $ - $ C = \left| \left\{ P \in \mathcal{P} \mid \text{cost}(P) = S_{\min} \right\} \right| \mod (10^9 + 7) $ Output: $ S_{\min} $ and $ C $.

API Response (JSON)

{
  "problem": {
    "name": "E. Exciting Acts",
    "description": {
      "content": "Aram has decided to make an autobiographical play about his life. His script has $N$ scenes with varying levels of excitement. For example, the scene of him studying for his first year exam was not ve",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10236E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Aram has decided to make an autobiographical play about his life. His script has $N$ scenes with varying levels of excitement. For example, the scene of him studying for his first year exam was not ve...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be an even integer, $ 2 \\leq N \\leq 74 $.  \nLet $ X = (x_0, x_1, \\dots, x_{N-1}) $ be a sequence of non-negative integers, $ 0 \\leq x_i \\leq 1000 $.  \nLet $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments