fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. int n,q; cin >> n >> q;
  6. string s; cin >> s;
  7. int l,r;
  8. for(int i = 0; i < n; i++) { // first food position
  9. if(s[i] == 'F') {
  10. l = i;
  11. break;
  12. }
  13. }
  14.  
  15. for(int i = n-1; i >= 0; i--) { // last food position
  16. if(s[i] == 'F') {
  17. r = i;
  18. break;
  19. }
  20. }
  21.  
  22. int dirt = 0, food = 0;
  23. for(int i = l; i <= r; i++) {
  24. if(s[i] == 'D') dirt++;
  25. if(s[i] == 'F') food++;
  26. }
  27.  
  28. int mid = food/2 + food % 2; // it is always optimal to gather the food around the median
  29. int cnt = 0, idx;
  30. for(int i = l; i <= r; i++) {
  31. if(s[i] == 'F') cnt++;
  32. if(cnt == mid) {
  33. idx = i;
  34. break;
  35. }
  36. }
  37.  
  38. //before mid
  39. int prev = 0, shift = 0;
  40. cnt = 0;
  41. for(int i = l; i < idx; i++) {
  42. if(s[i] == 'F') cnt++;
  43. else prev += cnt;
  44. }
  45. // after mid
  46. cnt = 0, shift = prev, prev = 0;
  47. for(int i = r; i >= idx; i--) {
  48. if(s[i] == 'F') cnt++;
  49. else prev += cnt;
  50. }
  51. shift += prev;
  52.  
  53. while(q--) {
  54. int x,y; cin >> x >> y; // x -> shifting food to adjacent , y -> cleaning the dirt
  55. cout << (dirt*y) + (shift*x) << "\n";
  56. }
  57.  
  58. }
Success #stdin #stdout 0s 5588KB
stdin
5 1
FEDEF
1 2
stdout
5