fork download
copy 
  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
comments (?)
stdin
copy 
5 1
FEDEF
1 2
stdout
copy 
5
https://ideone.com/thBN2d
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!