[CCC 2023 J4/S1] Trianglane

Luogu

IDLGP9302

Time1000ms

Memory512MB

DifficultyP2

2023CCC（加拿大）

Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally spilled black paint on some of the tiles. Now, some of the tiles are wet and the other tiles are dry. Bocchi must place warning tape around the perimeters of all wet areas. Can you help her determine how many metres of tape she needs? The first triangular tile will point upwards. Each pair of adjacent tiles (that is, tiles that share a common side) will point in opposite directions. Each tile has a side length of $1$ metre. ## Input The first line of input will consist of one positive integer $C$, representing the number of columns. The next two lines will each consist of $C$ integers separated by spaces. Each integer represents the colour of a tile along the laneway, with `1` indicating that the tile is black (wet) and `0` indicating that the tile is white (dry). The following table shows how the available 15 marks are distributed: | Marks | Description | Bound | | :----------: | :---------- | :----------: | | 3 | The laneway is not very long, black tiles are never adjacent and the second row is fully white. | $C \le 2 \times 10^3$ | | 3 | The laneway is not very long, black tiles may be adjacent and the second row is fully white. | $C \le 2 \times 10^3$ | | 5 | The laneway is not very long, black tiles may be adjacent and may appear in the second row. | $C \le 2 \times 10^3$ | | 4 | The laneway may be very long, black tiles may be adjacent and may appear in the second row. | $C \le 2 \times 10^5$ | ## Output Output a single integer representing the length of tape Bocchi needs,in metres. [samples] ## Note **本题采用捆绑测试**。 - Subtask $1$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形不相邻，第二行全部为白色三角形。 - Subtask $2$（$3$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行全部为白色三角形。 - Subtask $3$（$5$ points）：$C \leq 2 \times 10^3$，黑色三角形可能相邻，第二行可能有黑色三角形。 - Subtask $4$（$4$ points）：$C \leq 2 \times 10^5$，黑色三角形可能相邻，第二行可能有黑色三角形。样例 $1$ 图解： ![](https://cdn.luogu.com.cn/upload/image_hosting/5tfc7u5b.png) 样例 $2$ 图解： ![](https://cdn.luogu.com.cn/upload/image_hosting/4e22mx61.png)

Samples

Input #1

5
1 0 1 0 1
0 0 0 0 0

Output #1

Input #2

7
0 0 1 1 0 1 0
0 0 1 0 1 0 0

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2023 J4/S1] Trianglane",
    "description": {
      "content": "Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9302"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bocchi the Builder just finished constructing her latest project: a laneway consisting of two rows of white equilateral triangular tiles. However, at the last moment, disaster struck! She accidentally...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments