fork download
copy 
  1. /*
  2.   2024 cùng những điều ước.
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std; 
  7.  
  8. #define pb push_back
  9. #define sz(x) (int)(x.size())
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend()
  12.  
  13. typedef long long ll; 
  14. typedef pair<int, int> ii; 
  15.  
  16. const ll LINF = 1e18; 
  17. const int INF = 1e9;
  18.  
  19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
  20.  
  21. template<typename T>
  22. bool maximize(T& a, const T& b) {
  23. 	if (b < a) return false; 
  24. 	a = b; 
  25. 	return true; 
  26. }
  27.  
  28. template<typename T>
  29. bool minimize(T& a, const T& b) {
  30. 	if (a < b) return false;
  31. 	a = b; 
  32. 	return true; 
  33. }
  34.  
  35. // Bài này để ý là w[i] > 0 nên mảng tổng tiền tố pref[] của w[] sẽ tăng nghiêm ngặt (>) 
  36. // => Duyệt qua số kẹo mà Bob có thể ăn 
  37. //		sau đó dùng tìm kiếm nhị phân để check có tồn tại vị trí pos sao cho pref[pos] = Bob_sum 
  38.  
  39. const int N = 2e5 + 5;   
  40.  
  41. int n;  
  42. int w[N];  
  43. int pref[N];  
  44.  
  45. void solve() {
  46. 	cin >> n; 
  47. 	for (int i = 1; i <= n; i++) {
  48. 		cin >> w[i];  
  49. 		pref[i] = pref[i - 1] + w[i];   
  50. 	}	
  51.  
  52. 	int best = 0, Bob_sum = 0;  
  53. 	for (int i = n; i >= 1; i--) {
  54. 		Bob_sum += w[i]; 
  55. 		int pos = lower_bound(pref + 1, pref + i, Bob_sum) - pref;
  56. 		if (pos < i && pref[pos] == Bob_sum) maximize(best, (n - i + 1) + pos);  
  57. 	}
  58.  
  59. 	cout << best << '\n'; 
  60. }
  61.  
  62. signed main() {
  63. 	ios::sync_with_stdio(0); cin.tie(0); 
  64. 	int t; 
  65. 	cin >> t; 
  66.  
  67. 	while (t--) {
  68. 		solve(); 
  69. 	}
  70.  
  71. 	return 0;  
  72. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
4
3
10 20 10
6
2 1 4 2 4 1
5
1 2 4 8 16
9
7 3 20 5 15 1 11 8 10
stdout
copy 
2
6
0
7
https://ideone.com/IpwdD4
language:
C++14 (gcc 8.3)
created:
1 year 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!