Guest User

Untitled

a guest
Jan 3rd, 2018
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. */
  3.  
  4. //#pragma GCC optimize("O3")
  5. #define _CRT_SECURE_NO_WARNINGS
  6. #include <fstream>
  7. #include <iostream>
  8. #include <string>
  9. #include <complex>
  10. #include <math.h>
  11. #include <set>
  12. #include <vector>
  13. #include <map>
  14. #include <queue>
  15. #include <stdio.h>
  16. #include <stack>
  17. #include <algorithm>
  18. #include <list>
  19. #include <ctime>
  20.  
  21. #include <memory.h>
  22. #include <assert.h>
  23.  
  24. #define y0 sdkfaslhagaklsldk
  25.  
  26. #define y1 aasdfasdfasdf
  27. #define yn askfhwqriuperikldjk
  28. #define j1 assdgsdgasghsf
  29. #define tm sdfjahlfasfh
  30. #define lr asgasgash
  31. #define norm asdfasdgasdgsd
  32. #define have adsgagshdshfhds
  33. #define ends asdgahhfdsfshdshfd
  34.  
  35. #define eps 1e-8
  36. #define M_PI 3.141592653589793
  37. #define bsize 512
  38.  
  39. #define ldouble long double
  40. using namespace std;
  41.  
  42. #define bs 1000000007
  43.  
  44. const int N = 600031;
  45.  
  46. int n,ar[N];
  47. long long S[N];
  48.  
  49. long long sparse_gcd[20][N],sparse_s[20][N],sparse_max[20][N];
  50.  
  51. int gcd(int a,int b){
  52.     b=abs(b);
  53.     while (a&&b)a>b?a%=b:b%=a;
  54.     return a+b;
  55. }
  56.  
  57. vector<pair<long long, long long> > order;
  58.  
  59. long long suf_max[N];
  60.  
  61. int main(){
  62. //  freopen("apache.in","r",stdin);
  63. //  freopen("apache.out","w",stdout);
  64.     //freopen("input.txt", "r", stdin);
  65.     //freopen("output.txt", "w", stdout);
  66.     ios_base::sync_with_stdio(0);
  67. //  cin.tie(0);
  68.  
  69.     cin>>n;
  70.     long long ttl=0;
  71.  
  72.     for (int i=1;i<=n;i++){
  73.         cin>>ar[i];
  74.         S[i]=S[i-1]+ar[i];
  75.     }
  76.  
  77.     suf_max[n]=S[n];
  78.     for (int i=n-1;i>=0;--i)
  79.         suf_max[i]=max(suf_max[i+1],S[i]);
  80.  
  81.     long long ans=-1e18;
  82.  
  83.     order.clear();
  84.     for (int i=1;i<=n;i++){
  85.         order.push_back(make_pair(S[i],i));
  86.     }
  87.  
  88.     sort(order.begin(),order.end());
  89.  
  90.     long long MX=order.back().first;
  91.  
  92.     srand(time(NULL));
  93.  
  94.     if (rand()%2)
  95.         random_shuffle(order.begin(),order.end());
  96.  
  97.     for (int ii=0;ii<order.size();ii++){
  98.         int i=order[ii].second;
  99.         ttl=MX-order[ii].first;
  100.         long long cur_gcd=0;
  101.         int cur_max=-1e9;
  102.         long long cur_s=0;
  103.         for (int j=i;j<=n;j++){
  104.             cur_gcd=gcd(cur_gcd,ar[j]);
  105.             cur_max=max(cur_max,ar[j]);
  106.             cur_s+=ar[j];
  107.             long long here=cur_gcd*(cur_s-cur_max);
  108.             if (cur_gcd*1ll*(suf_max[j]-order[ii].first)<=ans)
  109.                 break;
  110.             if (here>ans)
  111.                 ans=here;
  112.         }
  113.         if (clock()*1.0/CLOCKS_PER_SEC>1.98)
  114.             break;
  115.     }
  116.     cout<<ans<<endl;
  117.  
  118.     cin.get(); cin.get();
  119.     return 0;
  120. }
RAW Paste Data