abdukodir

Untitled

Mar 7th, 2016
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <assert.h>
  5. #include <vector>
  6. #include <string>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <stack>
  11. #include <cstring>
  12. #include <algorithm>
  13. #define sc scanf
  14. #define pr printf
  15. #define pb push_back
  16. #define mp std::make_pair
  17. #define fr first
  18. #define se second
  19.  
  20. using namespace std;
  21.  
  22. typedef std::pair<int, int> pii;
  23. typedef std::pair<double, double> pdd;
  24.  
  25. const int MN = 1000010;
  26. const long long M = -(1LL << 50);
  27. const long long MAX_LONG = std::numeric_limits<long long>::max();
  28. const long long MIN_LONG = std::numeric_limits<long long>::min() + (1LL << 54);
  29. const int MAX_INT = std::numeric_limits<int>::max();
  30. const int MIN_INT = std::numeric_limits<int>::min();
  31.  
  32. long long l[MN], r[MN];
  33. int n, a, b, T;
  34. char s[MN];
  35.  
  36. int main() {
  37. //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  38. //freopen("path.in", "r", stdin); freopen("path.out", "w", stdout);
  39.  
  40. sc("%d%d%d%d", &n, &a, &b, &T);
  41. sc(" %s", s);
  42.  
  43. for (int i = n - 1; i > 0; i--) {
  44. l[n - i] = l[n - i - 1] + 1 + (s[i] == 'w') * 1LL * b;
  45. }
  46.  
  47. for (int i = 1; i < n; i++) {
  48. r[i] = r[i - 1] + 1 + (s[i] == 'w') * 1LL * b;
  49. }
  50. /*
  51. for (int i = 0; i < n; i++) {
  52. pr("%d %d\n", l[i], r[i]);
  53. }
  54. */
  55. int t = 1 + (s[0] == 'w') * b;
  56. if (t > T) {
  57. pr("0\n");
  58. return 0;
  59. }
  60.  
  61. T -= t;
  62. int ans = 1;
  63.  
  64. for (int k = 0; k < 2; k++) {
  65. int j = n - 1;
  66. for (int i = 0; i < n; i++) {
  67. /*
  68. pr("-> %d %d\n", l[i] + i * a, T);
  69. */
  70. if (1LL * l[i] + 1LL * i * a > 1LL * T) {
  71. break;
  72. }
  73.  
  74. while (j > 0 && (1LL * l[i] + 1LL * (i + 1LL * i + j) * 1LL * a + r[j]) > 1LL * T) {
  75. //pr("%d %d\n", j, (l[i] + (i + i + j) * a + r[j]));
  76. j--;
  77. }
  78. ans = max(ans, i + j + 1);
  79. }
  80. swap(l, r);
  81. }
  82.  
  83. pr("%d\n", min(n, ans));
  84.  
  85. return 0;
  86. }
Add Comment
Please, Sign In to add comment