D. Financiers Game

Codeforces

IDCF737D

Time2000ms

Memory512MB

Difficulty—

dpgames

English · Original

Chinese · Translation

Formal · Original

_This problem has unusual memory constraint._ At evening, Igor and Zhenya the financiers became boring, so they decided to play a game. They prepared _n_ papers with the income of some company for some time periods. Note that the income can be positive, zero or negative. Igor and Zhenya placed the papers in a row and decided to take turns making moves. Igor will take the papers from the left side, Zhenya will take the papers from the right side. Igor goes first and takes 1 or 2 (on his choice) papers from the left. Then, on each turn a player can take _k_ or _k_ + 1 papers from his side if the opponent took exactly _k_ papers in the previous turn. Players can't skip moves. The game ends when there are no papers left, or when some of the players can't make a move. Your task is to determine the difference between the sum of incomes on the papers Igor took and the sum of incomes on the papers Zhenya took, assuming both players play optimally. Igor wants to maximize the difference, Zhenya wants to minimize it. ## Input The first line contains single positive integer _n_ (1 ≤ _n_ ≤ 4000) — the number of papers. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 105 ≤ _a__i_ ≤ 105), where _a__i_ is the income on the _i_\-th paper from the left. ## Output Print the difference between the sum of incomes on the papers Igor took and the sum of incomes on the papers Zhenya took, assuming both players play optimally. Igor wants to maximize the difference, Zhenya wants to minimize it. [samples] ## Note In the first example it's profitable for Igor to take two papers from the left to have the sum of the incomes equal to 4. Then Zhenya wouldn't be able to make a move since there would be only one paper, and he would be able to take only 2 or 3..

_This problem has unusual memory constraint._ 在傍晚，金融家 Igor 和 Zhenya 感到无聊，于是决定玩一个游戏。他们准备了 #cf_span[n] 张纸，每张纸上写有一个公司在某个时间段的收入。注意，收入可以是正数、零或负数。 Igor 和 Zhenya 将这些纸排成一行，并决定轮流进行操作。Igor 从左侧取纸，Zhenya 从右侧取纸。Igor 先手，他可以选择从左侧取 #cf_span[1] 张或 #cf_span[2] 张纸。此后，每一轮玩家可以取 #cf_span[k] 张或 #cf_span[k + 1] 张纸，前提是对手在上一轮恰好取了 #cf_span[k] 张纸。玩家不能跳过回合。当纸张被取完，或某位玩家无法进行合法操作时，游戏结束。你的任务是，在双方都采取最优策略的前提下，计算 Igor 取得的纸张收入总和与 Zhenya 取得的纸张收入总和之差。Igor 希望最大化这个差值，Zhenya 希望最小化它。第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 4000]) —— 纸张的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 105 ≤ ai ≤ 105])，其中 #cf_span[ai] 表示从左数第 #cf_span[i] 张纸上的收入。请输出在双方都采取最优策略的前提下，Igor 取得的收入总和与 Zhenya 取得的收入总和之差。Igor 希望最大化该差值，Zhenya 希望最小化它。在第一个例子中，Igor 从左侧取两张纸，使收入总和为 #cf_span[4] 是有利的。此时 Zhenya 无法进行操作，因为只剩一张纸，而他只能取 #cf_span[2] 或 #cf_span[3] 张。 ## Input 第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 4000]) —— 纸张的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 105 ≤ ai ≤ 105])，其中 #cf_span[ai] 表示从左数第 #cf_span[i] 张纸上的收入。 ## Output 请输出在双方都采取最优策略的前提下，Igor 取得的收入总和与 Zhenya 取得的收入总和之差。Igor 希望最大化该差值，Zhenya 希望最小化它。 [samples] ## Note 在第一个例子中，Igor 从左侧取两张纸，使收入总和为 #cf_span[4] 是有利的。此时 Zhenya 无法进行操作，因为只剩一张纸，而他只能取 #cf_span[2] 或 #cf_span[3] 张。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of papers. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers representing incomes. Let $ I $ and $ Z $ denote the total income sums collected by Igor and Zhenya, respectively. **Game Rules** - Igor moves first, taking either 1 or 2 papers from the **left**. - Subsequent moves: if the opponent took $ k $ papers in the previous turn, the current player must take either $ k $ or $ k+1 $ papers from **their own side** (Igor: left, Zhenya: right). - Players alternate turns. The game ends when no papers remain or a player cannot make a valid move. **Objective** Compute $ I - Z $, assuming both players play optimally: - Igor maximizes $ I - Z $, - Zhenya minimizes $ I - Z $. **Constraints** $ 1 \leq n \leq 4000 $, $ -10^5 \leq a_i \leq 10^5 $.

Samples

Input #1

3
1 3 1

Output #1

Input #2

5
-1 -2 -1 -2 -1

Output #2

Input #3

4
-4 -2 4 5

Output #3

\-13

API Response (JSON)

{
  "problem": {
    "name": "D. Financiers Game",
    "description": {
      "content": "_This problem has unusual memory constraint._ At evening, Igor and Zhenya the financiers became boring, so they decided to play a game. They prepared _n_ papers with the income of some company for so",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF737D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_This problem has unusual memory constraint._\n\nAt evening, Igor and Zhenya the financiers became boring, so they decided to play a game. They prepared _n_ papers with the income of some company for so...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_This problem has unusual memory constraint._\n\n在傍晚，金融家 Igor 和 Zhenya 感到无聊，于是决定玩一个游戏。他们准备了 #cf_span[n] 张纸，每张纸上写有一个公司在某个时间段的收入。注意，收入可以是正数、零或负数。\n\nIgor 和 Zhenya 将这些纸排成一行，并决定轮流进行操作。Igor 从左侧取纸，Zhenya 从右侧取纸。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of papers.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers representing incomes.  \nLet $ I $ and $ Z $ denote the total income...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments