Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cmath>
- #include <assert.h>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <queue>
- #include <stack>
- #include <cstring>
- #include <algorithm>
- #define sc scanf
- #define pr printf
- #define pb push_back
- #define mp std::make_pair
- #define fr first
- #define se second
- using namespace std;
- typedef std::pair<int, int> pii;
- typedef std::pair<double, double> pdd;
- const int MN = 1000010;
- const long long M = -(1LL << 50);
- const long long MAX_LONG = std::numeric_limits<long long>::max();
- const long long MIN_LONG = std::numeric_limits<long long>::min() + (1LL << 54);
- const int MAX_INT = std::numeric_limits<int>::max();
- const int MIN_INT = std::numeric_limits<int>::min();
- long long l[MN], r[MN];
- int n, a, b, T;
- char s[MN];
- int main() {
- //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
- //freopen("path.in", "r", stdin); freopen("path.out", "w", stdout);
- sc("%d%d%d%d", &n, &a, &b, &T);
- sc(" %s", s);
- for (int i = n - 1; i > 0; i--) {
- l[n - i] = l[n - i - 1] + 1 + (s[i] == 'w') * 1LL * b;
- }
- for (int i = 1; i < n; i++) {
- r[i] = r[i - 1] + 1 + (s[i] == 'w') * 1LL * b;
- }
- /*
- for (int i = 0; i < n; i++) {
- pr("%d %d\n", l[i], r[i]);
- }
- */
- int t = 1 + (s[0] == 'w') * b;
- if (t > T) {
- pr("0\n");
- return 0;
- }
- T -= t;
- int ans = 1;
- for (int k = 0; k < 2; k++) {
- int j = n - 1;
- for (int i = 0; i < n; i++) {
- /*
- pr("-> %d %d\n", l[i] + i * a, T);
- */
- if (1LL * l[i] + 1LL * i * a > 1LL * T) {
- break;
- }
- while (j > 0 && (1LL * l[i] + 1LL * (i + 1LL * i + j) * 1LL * a + r[j]) > 1LL * T) {
- //pr("%d %d\n", j, (l[i] + (i + i + j) * a + r[j]));
- j--;
- }
- ans = max(ans, i + j + 1);
- }
- swap(l, r);
- }
- pr("%d\n", min(n, ans));
- return 0;
- }
Add Comment
Please, Sign In to add comment