Codeforces Round 909 (Div. 3) 1899B - 250 Thousand Tons of TNT Solution

 Problem Link:  https://codeforces.com/problemset/problem/1899/B

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. #define int long long
5. int32_t main() {
6. ios_base::sync_with_stdio(0);
7. cin.tie(0);
8. int t;
9. cin >> t;
10. while (t--) {
11. int n ; cin >> n ;
12. vector<int > a(n) ;
13. for ( int i = 0 ; i < n ; i++){
14. cin >> a[i] ;
15. }
16. vector<int>divisor ;
17. for ( int i = 1 ; i * i <= n ; i++){
18. if ( n % i == 0){
19. divisor.push_back(i) ;
20. if( i * i != n){
21. divisor.push_back(n/i) ;
22. }
23. }
24. }
25. sort(divisor.begin(),divisor.end()) ;
26. int ans = 0 ;
27. for ( auto size : divisor){
28. int cnt = 0 ;
29. int mn = LLONG_MAX ;
30. int mx = 0 ;
31. int tem_sum = 0 ;
32. for ( int i = 0 ; i < n ; i++){
33. tem_sum += a[i] ;
34. cnt++ ;
35. if ( cnt == size){
36. mn = min(mn,tem_sum) ;
37. mx = max(mx,tem_sum) ;
38. cnt = 0 ;
39. tem_sum = 0 ;
40. }
41. ans = max(ans,mx-mn) ;
42. }
43. }
44. cout << ans << '\n' ;
45. }
46. return 0 ;
47. }