[CEOI 2021] Tortoise

Luogu

IDLGP8175

Time3000ms

Memory512MB

DifficultyP7

2021CEOI（中欧）

Wilco 想购买糖果，为此它将访问 Nakamise 商店街。 Tom 想让 Wilco 少吃点糖果，为此它将在 Wilco 前购买一些糖果。商店街上共有 $N$ 个等距离的地点，它们要么是商店要么是空地。每家商店都有一定数量的糖果（可能为 $0$） Wilco 将会从第一个地点走到最后一个，顺序访问所有地点。每当它到达一家商店时它会买走所有糖果。Tom 每一刻的移动速度是 Wilco 的两倍，且可以朝两个方向移动。但是，Tom 每一刻只能携带最多一颗糖果。一旦 Tom 拿到一颗糖果，它就会把它带走直到把它交给在空地上玩的小孩。假设购买和给出糖果均不消耗时间。 Tom 的目标是最小化 Wilco 能拿到的糖果。初始时它们均在第一个地点，Tom 任何时刻先于 Wilco 行动。即如果第一个地点是商店，Tom 可以先于 Wilco 购买一颗糖果。那么在 Tom 的干扰下 Wilco 能拿到多少糖果呢？ ## Input 输入的第一行包含一个整数 $N$，含义如题目描述。第二行有 $N$ 个整数 $a_1,a_2,\dots,a_N$ 表示商店街上的 $N$ 个地点，其中 $a_i=-1$ 时第 $i$ 个地点为空地，否则它为商店且有 $a_i$ 颗糖果出售。有可能一家商店没有糖果（即 $a_i=0$）保证至少有一个地点是空地。 ## Output 输出 Wilco 将会买到的糖果数量。 [samples] ## Background 译自 CEOI2021 Day2 T2. [Tortoise](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。 ## Note #### 数据范围与约定对于 $100\%$ 的数据：$1\leq n \leq 5\times 10^5$，$-1\leq a_i \leq 10^4$。 | 子任务 | 分值 | 约束 | | :----: | :--: | :-----------------------------------------------: | | $1$ | $8$ | $1\leq N\leq 20$，$-1\leq a_i\leq 1$ | | $2$ | $10$ | $1\leq N\leq 300$，$-1\leq a_i\leq 1$ | | $3$ | $30$ | $1\leq N\leq 300$，$-1\leq a_i\leq 10^4$ | | $4$ | $25$ | $1\leq N\leq 5\times 10^3$，$-1\leq a_i\leq 10^4$ | | $5$ | $27$ | $1\leq N\leq 5\times 10^5$，$-1\leq a_i\leq 10^4$ |

Samples

Input #1

5
-1 1 1 1 1

Output #1

Input #2

8
-1 1 0 0 -1 0 0 3

Output #2

Input #3

8
2 -1 2 -1 2 -1 2 -1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2021] Tortoise",
    "description": {
      "content": "Wilco 想购买糖果，为此它将访问 Nakamise 商店街。 Tom 想让 Wilco 少吃点糖果，为此它将在 Wilco 前购买一些糖果。商店街上共有 $N$ 个等距离的地点，它们要么是商店要么是空地。 每家商店都有一定数量的糖果（可能为 $0$） Wilco 将会从第一个地点走到最后一个，顺序访问所有地点。每当它到达一家商店时它会买走所有糖果。Tom 每一刻的移动速度是 Wilco 的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8175"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Wilco 想购买糖果，为此它将访问 Nakamise 商店街。\n\nTom 想让 Wilco 少吃点糖果，为此它将在 Wilco 前购买一些糖果。商店街上共有 $N$ 个等距离的地点，它们要么是商店要么是空地。\n\n每家商店都有一定数量的糖果（可能为 $0$） Wilco 将会从第一个地点走到最后一个，顺序访问所有地点。每当它到达一家商店时它会买走所有糖果。Tom 每一刻的移动速度是 Wilco 的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments