fork download
copy 
  1. //Su dung deque co do phuc tap O(2n) 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define all(a) (a).begin(), (a).end()
  7. const int maxn = 1e3 + 1;
  8. int val(char c) {
  9. 	if (c >= '0' && c <= '9') return c - 48;
  10. 	return c - 65 + 10;
  11. }
  12. int A[maxn];
  13. deque<int> dq;
  14. int main() {
  15. 	ios_base::sync_with_stdio(false);
  16. 	cin.tie(0);
  17. 	cout.tie(0);
  18. 	string s;
  19. 	int t, answer = INT_MAX;
  20. 	cin >> t;
  21. 	while (t--) {
  22. 		int k, t, truyvan, result = 0;
  23. 		cin >> s;
  24. 		for (int i = 0; i < s.size(); ++i) {
  25. 			A[i] = val(s[i]);
  26. 		}
  27. 		for (int k = 1; k <= s.size(); ++k) {
  28. 			dq.clear();
  29. 			int ma = 0;
  30. 			for (int i = 0; i < s.size(); ++i) {
  31. 				while (!dq.empty() && A[i] <= A[dq.back()]) {
  32. 					dq.pop_back();
  33. 				}
  34. 				dq.push_back(i);
  35. 				if (dq.front() <= i - k) {
  36. 					dq.pop_front();
  37. 				}
  38. 				if (i >= k - 1) {
  39. 					ma = max(ma, k * A[dq.front()]);
  40. 				}
  41. 			}
  42. 			result = max(result, ma);
  43. 		}
  44. 		answer = min(answer, result);
  45. 	}
  46. 	cout << answer;
  47.  
  48. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
3 
23AF45 
5556666 
CAEABBF
stdout
copy 
20
https://ideone.com/FIbdgl
min trên đoạn con tịnh tiến sử dụng deque
language:
C++14 (gcc 8.3)
created:
8 days 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!