| 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 | ||||