#PU1396. USACO 2024 February Contest, Bronze — Problem 2. Milk Exchange

USACO 2024 February Contest, Bronze — Problem 2. Milk Exchange

USACO 2024 February Contest, Bronze — Problem 2. Milk Exchange

题目描述

Farmer John's NN (1≤N≤2⋅105)(1 \leq N \leq 2 \cdot 10^5) cows are lined up in a circle such that for each ii in 1,2,…,N−11,2,\dots,N-1, the cow to the right of cow ii is cow i+1i+1, and the cow to the right of cow NN is cow 11. The iith cow has a bucket with integer capacity aia_i (1≤ai≤109)(1 \leq a_i \leq 10^9) liters. All buckets are initially full. Every minute, the cows exchange milk according to a string s1s2…sNs_1s_2\dots s_N consisting solely of the characters ‘L’\text{‘L’} and ‘R’\text{‘R’}. if the iith cow has at least 11 liter of milk, she will pass 11 liter of milk to the cow to her left if si=‘L’s_i=\text{‘L’}, or to the right if si=‘R’s_i=\text{‘R’}. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away a liter of milk but also receives a liter, her milk is preserved). If a cow's total milk ever ends up exceeding aia_i, then the excess milk will be lost. FJ wants to know: after MM minutes (1≤M≤109(1 \leq M \leq 10^9), what is the total amount of milk left among all cows?

输入格式

The first line contains NN and MM. The second line contains a string s1s2…sNs_1s_2\dots s_N consisting solely of the characters ‘L’\text{‘L’} or ‘R’\text{‘R’}, denoting the direction each cow will pass their milk in. The third line contains integers a1,a2,…,aNa_1, a_2, \dots, a_N, the capacities of each bucket.

输出格式

(见题面原文)

数据范围

Inputs 4-8: N,M≤1000N,M \le 1000 Inputs 9-16: No additional Problem credits: Chongtian Ma, Alex Liang

样例

样例 1

3 1
RRL
1 1 1
2
Cows $2$ and $3$ pass each other one liter of milk, so their milk is preserved.
When cow $1$ passes their milk to cow $2$, cow $2$'s bucket overflows, and one
liter of milk is lost after one minute.

样例 2

5 20
LLLLL
3 3 2 3 3
14
Each cow is passing a liter of milk to the cow on the left and gaining a liter
of milk from the cow on the right, so all of the milk is preserved regardless of
how much time passes.

样例 3

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4
38
Initially, there are a total of 51 liters of milk. After 5 minutes, cows $3$, $6$, and $7$ will lose 5, 3, and 5 liters of milk respectively. Therefore, a total of 38 liters of milk remain.

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).