10067 2024. 03. 26 09:21:17 szil Nemzetközi Rántott Hús Fesztivál cpp17 Elfogadva 100/100 109ms 14408 KiB 
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 1'000'001;

struct State {
    int res = 0, extra = 0, upgraded = 0;
};

State operator+(State a, State b) {
    return {a.res + b.res, a.extra + b.extra, a.upgraded + b.upgraded};
}

char s[MAXN];
int ans[MAXN];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    
    stack<State> blocked;
    State curr;
    for (int i = n; i >= 1; i--) {
        if (s[i] == 'H') {
            blocked.push(curr);
            curr = State();
        } else  {
            bool used = true;
            if (blocked.empty()) {
                if (curr.upgraded) {
                    curr.upgraded--;
                    curr.res++;
                } else if (curr.extra) {
                    curr.extra--;
                    curr.upgraded++;
                } else {
                    used = false;
                }
                
            } else {
                curr = curr + blocked.top(); 
                curr.res++;
                blocked.pop();
            }
            if (s[i] == 'M') {
                if (used) curr.extra++;
                else curr.upgraded++;
            }
        }

        ans[i] = curr.res;
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1836 KiB
2 Elfogadva 3ms 2188 KiB
subtask2 7/7
3 Elfogadva 2ms 2112 KiB
4 Elfogadva 3ms 2244 KiB
subtask3 9/9
5 Elfogadva 3ms 2484 KiB
6 Elfogadva 3ms 2476 KiB
7 Elfogadva 3ms 2744 KiB
subtask4 14/14
8 Elfogadva 108ms 12608 KiB
9 Elfogadva 109ms 12748 KiB
10 Elfogadva 108ms 12884 KiB
11 Elfogadva 109ms 13104 KiB
12 Elfogadva 100ms 13228 KiB
13 Elfogadva 105ms 13448 KiB
14 Elfogadva 101ms 13640 KiB
15 Elfogadva 100ms 13696 KiB
subtask5 11/11
16 Elfogadva 3ms 3884 KiB
17 Elfogadva 3ms 4008 KiB
18 Elfogadva 3ms 4084 KiB
subtask6 29/29
19 Elfogadva 3ms 4108 KiB
20 Elfogadva 3ms 4160 KiB
21 Elfogadva 3ms 4152 KiB
22 Elfogadva 3ms 4112 KiB
subtask7 30/30
23 Elfogadva 108ms 13944 KiB
24 Elfogadva 108ms 13888 KiB
25 Elfogadva 108ms 13992 KiB
26 Elfogadva 108ms 13916 KiB
27 Elfogadva 107ms 13932 KiB
28 Elfogadva 107ms 13916 KiB
29 Elfogadva 105ms 13844 KiB
30 Elfogadva 107ms 13844 KiB
31 Elfogadva 107ms 13836 KiB
32 Elfogadva 105ms 14052 KiB
33 Elfogadva 104ms 14036 KiB
34 Elfogadva 105ms 14060 KiB
35 Elfogadva 104ms 14160 KiB
36 Elfogadva 101ms 14300 KiB
37 Elfogadva 104ms 14408 KiB
38 Elfogadva 100ms 14212 KiB
39 Elfogadva 100ms 14228 KiB
40 Elfogadva 104ms 14268 KiB