12842022-03-29 21:47:25Valaki2Nemzetközi Rántott Hús Fesztiválcpp14Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1848 KiB
2Elfogadva71ms1992 KiB
subtask27/7
3Elfogadva1ms1868 KiB
4Elfogadva1ms1868 KiB
subtask39/9
5Elfogadva20ms1928 KiB
6Elfogadva13ms1952 KiB
7Elfogadva70ms1952 KiB
subtask40/14
8Időlimit túllépés589ms10968 KiB
9Időlimit túllépés587ms11948 KiB
10Időlimit túllépés591ms12920 KiB
11Időlimit túllépés575ms13852 KiB
12Időlimit túllépés550ms14832 KiB
13Időlimit túllépés575ms15808 KiB
14Időlimit túllépés570ms16796 KiB
15Időlimit túllépés577ms17840 KiB
subtask511/11
16Elfogadva2ms9776 KiB
17Elfogadva2ms9788 KiB
18Elfogadva2ms9792 KiB
subtask629/29
19Elfogadva76ms9848 KiB
20Elfogadva82ms9924 KiB
21Elfogadva86ms9940 KiB
22Elfogadva86ms9876 KiB
subtask70/30
23Időlimit túllépés564ms18948 KiB
24Időlimit túllépés575ms19800 KiB
25Időlimit túllépés577ms20856 KiB
26Időlimit túllépés513ms21892 KiB
27Időlimit túllépés513ms20032 KiB
28Időlimit túllépés519ms15088 KiB
29Időlimit túllépés510ms14664 KiB
30Időlimit túllépés528ms14456 KiB
31Időlimit túllépés501ms15544 KiB
32Időlimit túllépés545ms16424 KiB
33Időlimit túllépés542ms15072 KiB
34Időlimit túllépés587ms15708 KiB
35Időlimit túllépés542ms16672 KiB
36Időlimit túllépés572ms16224 KiB
37Időlimit túllépés578ms16868 KiB
38Időlimit túllépés578ms17932 KiB
39Időlimit túllépés574ms18860 KiB
40Időlimit túllépés577ms19968 KiB