fork download
copy 
  1. /* صل علي محمد ﷺ*/
  2.  
  3.  
  4. #include                   <bits/stdc++.h>
  5. //#include <ext/pb_ds/assoc_container.hpp>
  6. //#include <ext/pb_ds/tree_policy.hpp>
  7. //using namespace __gnu_pbds;
  8. #include                   <unordered_map>
  9. #include                   <unordered_set>
  10. #define IOS                ios_base::sync_with_stdio(0);\
  11.                            cin.tie(NULL);cout.tie(NULL); 
  12. #define OO                 0x3f3f3f3f
  13. #define endd               "\n"
  14. #define sett               cout<< fixed << showpoint\
  15.                            << setprecision
  16. #define ff                 first
  17. #define ss                 second
  18. #define sz(s)              ((int)(s).size())
  19. #define all(v)             (v).begin(),(v).end()
  20. #define rall(v)            (v).rbegin(),(v).rend()
  21. #define File ofstream      coutt("outt.txt");\
  22.                            ifstream cinn("inn.txt");
  23. #define ordered_set        tree<int, null_type,\
  24.                            less_equal<int>, rb_tree_tag,\
  25.                            tree_order_statistics_node_update>
  26. #define pii                pair<int,int>
  27. typedef long long          ll;
  28. typedef double             dd;
  29. int dy[] = { -1, 1, 0, 0, -1, 1, 1, -1 };
  30. int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
  31. /// priority_queue<ll, vector<ll>, greater<ll>>q;
  32. using namespace std;
  33.  
  34. /* صل علي محمد ﷺ*/
  35.  
  36. vector<int> KMP(string& s) {
  37. 	int n = s.size();
  38. 	vector<int> fail(n);
  39. 	for (int i = 1; i < n; i++) {
  40. 		int j = fail[i - 1];
  41. 		while (j > 0 and s[j] != s[i])
  42. 			j = fail[j - 1];
  43.  
  44. 		j += s[i] == s[j];
  45. 		fail[i] = j;
  46. 	}
  47. 	return fail;
  48. }
  49.  
  50. void solve() {
  51.  
  52. 	ll n, x, y, z;
  53. 	cin >> n >> x >> y >> z;
  54. 	string s; cin >> s;
  55.  
  56. 	vector<int>pre = KMP(s);
  57. 	//for (int i = 0; i < n; i++)cout << pre[i]; cout << '\n';
  58. 	reverse(all(s));
  59. 	vector<int>suf = KMP(s);
  60. 	reverse(all(suf));
  61. 	int l = 1, r = n - 2;
  62. 	ll ans = 0;
  63.  
  64. 	//for (int i = 0; i < n; ++i)cout << i; cout << '\n';
  65.  
  66. 	while (l < r) {
  67.  
  68. 		if (!pre[l])l++;
  69. 		if (!suf[r])r--;
  70. 		if (!pre[l] || !suf[r])continue;
  71. 		if (l >= r)continue;
  72.  
  73. 		ll calc = pre[l] * x + suf[r] * y - z + (r - l) * z;
  74. 		//cout << l << ' ' << r <<' '<< calc << '\n';
  75. 		//cout << pre[l] << ' ' << suf[r] << '\n';
  76. 		ans = max(ans, calc);
  77. 		if (x >= z)	l++;
  78. 		if (y >= z) r--;
  79.  
  80. 		if (z >= x and z >= y)break;
  81.  
  82. 	}
  83. 	cout << ans;
  84.  
  85. }
  86.  
  87.  
  88. int main() {
  89. 	//freopen("Input.in", "r", stdin);
  90. 	//freopen("Output.txt", "w", stdout);
  91. 	IOS;
  92. 	//cout << mx;
  93. 	int test_cases = 1;
  94. 	//cin >> test_cases;
  95. 	for (int i = 1; i <= test_cases; i++) {
  96. 		solve();
  97. 		//cout << endd;
  98. 	}
  99. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Oi2ZW
language:
C++ (gcc 8.3)
created:
133 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!