1284 | 2022-03-29 21:47:25 | Valaki2 | Nemzetközi Rántott Hús Fesztivál | cpp14 | Időlimit túllépés 56/100 | 591ms | 21892 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 2ms | 1848 KiB | ||||
2 | Elfogadva | 71ms | 1992 KiB | ||||
subtask2 | 7/7 | ||||||
3 | Elfogadva | 1ms | 1868 KiB | ||||
4 | Elfogadva | 1ms | 1868 KiB | ||||
subtask3 | 9/9 | ||||||
5 | Elfogadva | 20ms | 1928 KiB | ||||
6 | Elfogadva | 13ms | 1952 KiB | ||||
7 | Elfogadva | 70ms | 1952 KiB | ||||
subtask4 | 0/14 | ||||||
8 | Időlimit túllépés | 589ms | 10968 KiB | ||||
9 | Időlimit túllépés | 587ms | 11948 KiB | ||||
10 | Időlimit túllépés | 591ms | 12920 KiB | ||||
11 | Időlimit túllépés | 575ms | 13852 KiB | ||||
12 | Időlimit túllépés | 550ms | 14832 KiB | ||||
13 | Időlimit túllépés | 575ms | 15808 KiB | ||||
14 | Időlimit túllépés | 570ms | 16796 KiB | ||||
15 | Időlimit túllépés | 577ms | 17840 KiB | ||||
subtask5 | 11/11 | ||||||
16 | Elfogadva | 2ms | 9776 KiB | ||||
17 | Elfogadva | 2ms | 9788 KiB | ||||
18 | Elfogadva | 2ms | 9792 KiB | ||||
subtask6 | 29/29 | ||||||
19 | Elfogadva | 76ms | 9848 KiB | ||||
20 | Elfogadva | 82ms | 9924 KiB | ||||
21 | Elfogadva | 86ms | 9940 KiB | ||||
22 | Elfogadva | 86ms | 9876 KiB | ||||
subtask7 | 0/30 | ||||||
23 | Időlimit túllépés | 564ms | 18948 KiB | ||||
24 | Időlimit túllépés | 575ms | 19800 KiB | ||||
25 | Időlimit túllépés | 577ms | 20856 KiB | ||||
26 | Időlimit túllépés | 513ms | 21892 KiB | ||||
27 | Időlimit túllépés | 513ms | 20032 KiB | ||||
28 | Időlimit túllépés | 519ms | 15088 KiB | ||||
29 | Időlimit túllépés | 510ms | 14664 KiB | ||||
30 | Időlimit túllépés | 528ms | 14456 KiB | ||||
31 | Időlimit túllépés | 501ms | 15544 KiB | ||||
32 | Időlimit túllépés | 545ms | 16424 KiB | ||||
33 | Időlimit túllépés | 542ms | 15072 KiB | ||||
34 | Időlimit túllépés | 587ms | 15708 KiB | ||||
35 | Időlimit túllépés | 542ms | 16672 KiB | ||||
36 | Időlimit túllépés | 572ms | 16224 KiB | ||||
37 | Időlimit túllépés | 578ms | 16868 KiB | ||||
38 | Időlimit túllépés | 578ms | 17932 KiB | ||||
39 | Időlimit túllépés | 574ms | 18860 KiB | ||||
40 | Időlimit túllépés | 577ms | 19968 KiB |