12842022-03-29 21:47:25Valaki2Nemzetközi Rántott Hús Fesztiválcpp14Time limit exceeded 56/100591ms21892 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int inf = 1e8 + 42;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    vector<int> ans(1 + n, 0);
    for(int l = 1; l <= n; l++) {
        vector<int> pref(1 + n, 0);
        int r = n;
        for(int i = l; i <= n; i++) {
            pref[i] += pref[i - 1];
            if(s[i] == 'H') {
                pref[i]--;
            } else {
                pref[i]++;
            }
            if(pref[i] < 0) {
                r = i - 1;
                break;
            }
        }
        if(r < l) {
            continue;
        }
        // off by one error (chance)
        if(r < n) {
            ans[l] = (r - l + 1) / 2;
            continue;
        }
        for(int i = l; i <= n; i++) {
            if(s[i] == 'H') {
                ans[l]++;
            }
        }
        int mini = inf;
        for(int i = n; i >= l; i--) {
            mini = min(mini, pref[i]);
            if(mini >= 2 && s[i] == 'M') {
                ans[l]++;
                mini -= 2;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1848 KiB
2Accepted71ms1992 KiB
subtask27/7
3Accepted1ms1868 KiB
4Accepted1ms1868 KiB
subtask39/9
5Accepted20ms1928 KiB
6Accepted13ms1952 KiB
7Accepted70ms1952 KiB
subtask40/14
8Time limit exceeded589ms10968 KiB
9Time limit exceeded587ms11948 KiB
10Time limit exceeded591ms12920 KiB
11Time limit exceeded575ms13852 KiB
12Time limit exceeded550ms14832 KiB
13Time limit exceeded575ms15808 KiB
14Time limit exceeded570ms16796 KiB
15Time limit exceeded577ms17840 KiB
subtask511/11
16Accepted2ms9776 KiB
17Accepted2ms9788 KiB
18Accepted2ms9792 KiB
subtask629/29
19Accepted76ms9848 KiB
20Accepted82ms9924 KiB
21Accepted86ms9940 KiB
22Accepted86ms9876 KiB
subtask70/30
23Time limit exceeded564ms18948 KiB
24Time limit exceeded575ms19800 KiB
25Time limit exceeded577ms20856 KiB
26Time limit exceeded513ms21892 KiB
27Time limit exceeded513ms20032 KiB
28Time limit exceeded519ms15088 KiB
29Time limit exceeded510ms14664 KiB
30Time limit exceeded528ms14456 KiB
31Time limit exceeded501ms15544 KiB
32Time limit exceeded545ms16424 KiB
33Time limit exceeded542ms15072 KiB
34Time limit exceeded587ms15708 KiB
35Time limit exceeded542ms16672 KiB
36Time limit exceeded572ms16224 KiB
37Time limit exceeded578ms16868 KiB
38Time limit exceeded578ms17932 KiB
39Time limit exceeded574ms18860 KiB
40Time limit exceeded577ms19968 KiB