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