[CCC 2024 S5] Chocolate Bar Partition

Luogu

IDLGP10299

Time1000ms

Memory512MB

DifficultyP6

2024CCC（加拿大）

Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。如果可以通过向上、向下、向左或向右移动的方式访问到每个小方块，则该部分被视为一个连通块。 ## Input 输入的第一行包含一个正整数 $N$ 表示巧克力的长度。第二行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第一行第 $j$ 个小方块的美味度 $T_{1,j}$。类似地，第三行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第二行第 $j$ 个小方块的美味度 $T_{2,j}$。 ## Output 输出一个整数，表示 Maxwell 最多能把巧克力切分出的连通块数。 [samples] ## Note **【样例 1 解释】** 把巧克力分割成 $2$ 块是最优的，一种方案是把右下角的一个小方块作为一个连通块，其余三个小方块作为第二个连通块，如下图所示。 ![](https://cdn.luogu.com.cn/upload/image_hosting/2yga1u9u.png) 每一个连通块的平均美味度都为 $5$。 **【样例 2 解释】** 一种获得平均分割巧克力的方案如下图所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/hty1ata8.png) 注意每一块的平均美味度都为 $1$。 **【数据范围】** **本题采用捆绑测试。** 对于所有数据，保证 $1 \leq N \leq 2 \times 10^5$，$0 \leq T_{i,j} \leq 10^8$。下面的表格显示了 $15$ 分的分配方案： | 分值 | $N$ 的范围 | $T_{i,j}$ 的范围 | | :-: | :-: | :-: | | $2$ | $N = 2$ | $0 \leq T_{i,j} \leq 5$ | | $2$ | $1 \leq N \leq 8$ | $0 \leq T_{i,j} \leq 20$ | | $1$ | $1 \leq N \leq 20$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 100$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 1000$ | $0 \leq T_{i,j} \leq 100$ | | $3$ | $1 \leq N \leq 2000$ | $0 \leq T_{i,j} \leq 10^5$ | | $3$ | $1 \leq N \leq 2 \times 10^5$ | $0 \leq T_{i,j} \leq 10^8$ |

Samples

Input #1

2
5 4
6 5

Output #1

Input #2

5
1 0 1 2 0
0 2 0 3 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2024 S5] Chocolate Bar Partition",
    "description": {
      "content": "Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \\times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。 如果可以通过向上、向下、向",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10299"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \\times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。\n\n如果可以通过向上、向下、向...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments