[USACO24FEB] Milk Exchange B

Luogu

IDLGP10188

Time2000ms

Memory256MB

DifficultyP4

数学USACO2024O2优化图论建模

Farmer John 的 $N$（$1\le N\le 2\cdot 10^5$）头奶牛排成一圈，使得对于 $1,2,\ldots,N−1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）升的桶。所有桶初始时都是满的。每一分钟，奶牛都会根据一个字符串 $s_1s_2\ldots s_N$ 传递牛奶，该字符串仅由字符 `L` 和 `R` 组成。当第 $i$ 头奶牛至少有 $1$ 升牛奶时，如果 $s_i=\texttt{L}$，她会将 $1$ 升牛奶传递给她左边的奶牛，如果 $s_i=\texttt R$ 则传递给右边的奶牛。所有交换同时发生（即，如果一头奶牛的桶是满的，送出一升牛奶，但也收到一升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。 FJ 想要知道：经过 $M$ 分钟（$1\le M\le 10^9$）后，所有奶牛总共还余下多少牛奶？ ## Input 输入的第一行包含 $N$ 和 $M$。第二行包含一个字符串 $s_1s_2\ldots s_N$，仅由字符 `L` 或 `R` 组成，表示每头奶牛传递牛奶的方向。第三行包含整数 $a_1,a_2,\ldots,a_N$，为每个桶的容量。 ## Output 输出一个整数，为 $M$ 分钟后所有奶牛总共余下的牛奶量。 **注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 `long long`）。** [samples] ## Note ### 样例解释 1 奶牛 $2$ 和 $3$ 互相传递一升牛奶，因此她们的牛奶得以保留。当奶牛 $1$ 将牛奶传递给奶牛 $2$ 时，奶牛 $2$ 的桶会溢出，从而一分钟后损失了一升牛奶。 ### 样例解释 2 每头奶牛都将一升牛奶传递给左边的奶牛，并从右边的奶牛那里获得一升牛奶，因此无论经过多长时间所有牛奶都会被保留下来。 ### 样例解释 3 初始时，共有 $51$ 升牛奶。$5$ 分钟后，奶牛 $3$，$6$ 和 $7$ 将分别损失 $5$，$3$ 和 $5$ 升牛奶。因此，总共还剩下 $38$ 升牛奶。 ### 测试点性质 - 测试点 $4-8$：$N,M\le 1000$。 - 测试点 $9-16$：没有额外限制。

Samples

Input #1

3 1
RRL
1 1 1

Output #1

Input #2

5 20
LLLLL
3 3 2 3 3

Output #2

Input #3

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO24FEB] Milk Exchange B",
    "description": {
      "content": "Farmer John 的 $N$（$1\\le N\\le 2\\cdot 10^5$）头奶牛排成一圈，使得对于 $1,2,\\ldots,N−1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。 每一分钟，奶牛都会根据一个字符串",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10188"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 的 $N$（$1\\le N\\le 2\\cdot 10^5$）头奶牛排成一圈，使得对于 $1,2,\\ldots,N−1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。\n\n每一分钟，奶牛都会根据一个字符串...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments