Advertisement
Guest User

Untitled

a guest
Apr 20th, 2021
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.65 KB | None | 0 0
  1. int dp[26][1501];
  2.  
  3. void solve(int tc) {
  4. memset(dp, -1, sizeof(dp));
  5. int N, Q;
  6. string S;
  7. cin >> N >> S >> Q;
  8. while(Q--) {
  9. int amount; cin >> amount;
  10. int storeAmount = amount;
  11. char C; cin >> C;
  12. if(dp[C - 'a'][amount] != -1) {
  13. cout << dp[C - 'a'][amount] << nl;
  14. continue;
  15. }
  16. int right = 0, left = 0;
  17. int mx = 0;
  18. while(right < N) {
  19. if(S[right] == C) {
  20. right++;
  21. }else if(S[right] != C && amount > 0) {
  22. right++;
  23. amount--;
  24. }else {
  25. if(S[left] != C) {
  26. amount++;
  27. }
  28. left++;
  29. }
  30. mx = max(mx, right - left);
  31. }
  32. cout << min(N, mx) << nl;
  33. dp[C - 'a'][storeAmount] = mx;
  34. }
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement