Milk Exchange

    1/*
    2bruce code
    3#include <bits/stdc++.h>
    4using namespace std;
    5typedef long long ll;
    6const int MM = 2e5+5;
    7int N, M, a[MM];  string s; ll ans, loss;
    8int main(){
    9    ios::sync_with_stdio(0); cin.tie(0);
    10    cin >> N >> M >> s;
    11    for(int i=0; i<N; i++) {
    12        cin >> a[i]; ans += a[i];
    13    }
    14    for(int i=0; i<N; i++) {
    15        if(s[i] == 'R' && s[(i+1)%N] == 'L') {
    16            ll sum = 0;
    17            for(int j=(i-1+N)%N; s[j]=='R'; j=(j-1+N)%N){
    18                sum += a[j];
    19            }
    20            loss += min((ll)M, sum);  sum = 0;
    21            for(int j=(i+2)%N; s[j]=='L'; j=(j+1)%N){
    22                sum += a[j];
    23            }
    24            loss += min((ll)M, sum);
    25        }
    26    }
    27    cout << ans - loss << "\n";
    28}*/
    29#include <bits/stdc++.h>
    30using namespace std;
    31const int MAXN = 200000 + 5;
    32int n;
    33long long m;
    34long long cap[MAXN];
    35int indeg[MAXN], nxtCow[MAXN], vis[MAXN];
    36int main() {
    37    ios::sync_with_stdio(0);
    38    cin.tie(0);
    39    cin >> n >> m;
    40    string s;
    41    cin >> s;
    42    s = "a" + s;// 1-index
    43    long long total = 0;
    44    for (int i = 1; i <= n; i++) {
    45        cin >> cap[i];
    46        total += cap[i];
    47    }
    48    // Build directed graph
    49    for (int i = 1; i <= n; i++) {
    50        int j;
    51        if (s[i] == 'L') {
    52            j = (i == 1 ? n : i - 1); // wrap around left
    53        } else {
    54            j = (i == n ? 1 : i + 1); // wrap around right
    55        }
    56        nxtCow[i] = j;
    57        indeg[j]++;  // j has one more incoming edge
    58    }
    59 
    60    // Start from all cows with indegree 0 (net givers)
    61    for (int i = 1; i <= n; i++) {
    62        if (!vis[i] && indeg[i] == 0) {
    63            vector<int> path;
    64            int cur = i;
    65            // Follow the chain until we reach a visited node(cycle)
    66            while (!vis[cur]) {
    67                vis[cur] = 1;
    68                path.push_back(cur);
    69                cur = nxtCow[cur];
    70            }
    71            // All nodes in path before the first occurrence of cur are non-cycle
    72            long long nonCycleSum = 0;
    73            for (int x : path) {
    74                if (x == cur) break;
    75                nonCycleSum += cap[x];
    76            }
    77            // This chain can lose at most min(m, sum of its non-cycle milk)
    78            total -= min(m, nonCycleSum);
    79        }
    80    }
    81    cout << total << '\n';
    82    return 0;
    83}
    84