fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. void solve() {
  6.     int n;
  7.     cin >> n;
  8.    vector<int> v(n);
  9.    for(int i=0;i<n;i++){
  10.    		cin>>v[i];
  11.    }
  12.    map<int,int> s;
  13.    for(int i=1;i<n;i++){
  14.    		if(n%i==0){
  15.    			s[i]++;
  16.    		}
  17.    }
  18.    vector<int> sum(n,0);
  19.    sum[0]=v[0];
  20.    for(int i=1;i<n;i++){
  21.    		sum[i]=v[i]+sum[i-1];
  22.    }
  23.    int ans=0;
  24.    for(auto l:s){
  25.    	int k=(l.first);
  26.    	int maxi=sum[k-1];
  27.    	int mini=sum[k-1];
  28.    	int t=sum[k-1];
  29.    	for(int i=2*k-1;i<n;i+=k){
  30.    		maxi=max(maxi,sum[i]-t);
  31.    		mini=min(mini,sum[i]-t);
  32.    		t=sum[i];
  33.    	}
  34.    	ans=max(ans,maxi-mini);
  35.    	// cout<<ans<<endl;
  36.  
  37.    }
  38.    cout<<ans<<endl;
  39.  
  40.  
  41. }
  42.  
  43. signed main() {
  44.     int t;
  45.     cin >> t;
  46.     while (t--) {
  47.         solve();
  48.     }
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198
stdout
copy 
1
9
0
189114
112141
https://ideone.com/mw6brV
language:
C++ (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!