Guest User

Untitled

a guest
Jan 3rd, 2018
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<string.h>
  7. using namespace std;
  8.  
  9. typedef long long LL;
  10. typedef vector<int> VI;
  11.  
  12. #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
  13. #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
  14. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  15.  
  16. template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
  17. template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
  18. template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
  19.     for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
  20.     putchar('\n');
  21. }
  22.  
  23. template<class T> struct IRXQ {
  24.     int n, g; T *d;
  25.     IRXQ() : n(0), g(0), d(NULL) {}
  26.     template<class Iter> IRXQ(Iter begin, Iter end) : n(0), g(0), d(0) { build(begin, end); }
  27.     IRXQ(const IRXQ &y) : n(y.n), g(0), d(NULL) { if (y.n) build(y.d[0], y.d[0] + n); }
  28.     IRXQ(IRXQ &&y) : n(0), g(0), d(NULL) { swap(*this, y); }
  29.     ~IRXQ() { if (n) { n = 0; delete d; d = NULL; } }
  30.     friend void swap(IRXQ &x, IRXQ &y) { swap(x.n, y.n); swap(x.d, y.d); }
  31.     IRXQ& operator=(IRXQ y) { swap(*this, y); return *this; }
  32.  
  33.     template<class Iter> void build(Iter begin, Iter end) { // random access iterator
  34.     n = end - begin;
  35.     if (n == 0) return;
  36.     g = __lg(n);
  37.     d = new T[n*(g+1)];
  38.     REP (i, n) { d[i] = *begin; ++begin; }
  39.     for (int t=0, b=0; t<g; t++, b+=n) for (int i=0, j=1<<t; j<=n-(1<<t); i++, j++)
  40.         d[b+n+i] = (d[b+i] < d[b+j]? d[b+j]: d[b+i]);
  41.     }
  42.  
  43.     const T at(int i) const { return d[i]; }
  44.  
  45.     const T max_v(int l, int r) const {
  46.     int h = __lg(r - l), b = n * h;
  47.     r -= 1<<h;
  48.     return d[b+l] < d[b+r]? d[b+r]: d[b+l];
  49.     }
  50.  
  51.     int max_i(int l, int r) const {
  52.     return first_more_equal(l, max_v(l, r));
  53.     }
  54.  
  55.     // for i in [l .. n-1]:
  56.     //   if at(i) > v: return i;
  57.     // return n;
  58.     int first_more_than(int l, const T v) const {
  59.     for (int t=g+1; t--; )
  60.         if (l + (1<<t) <= n && !(v < d[n*t+l]))
  61.         l += 1 << t;
  62.     return l;
  63.     }
  64.  
  65.     // for i in [l .. n-1]:
  66.     //   if v <= at(i): return i;
  67.     // return n;
  68.     int first_more_equal(int l, const T v) const {
  69.     for (int t=g+1; t--; )
  70.         if (l + (1<<t) <= n && d[n*t+l] < v)
  71.         l += 1 << t;
  72.     return l;
  73.     }
  74.  
  75.     // for i in [r-1 .. 0]:
  76.     //   if v < at(i): return i;
  77.     // return n;
  78.     int last_more_than(int r, const T v) const {
  79.     for (int t=g+1; t--; )
  80.         if (0 <= r - (1<<t) && !(v < d[n*t+r-(1<<t)]))
  81.         r -= 1 << t;
  82.     return r? r-1: n;
  83.     }
  84.  
  85.     // for i in [r-1 .. 0]:
  86.     //   if v <= at(i): return i;
  87.     // return n;
  88.     int last_more_equal(int r, const T v) const {
  89.     for (int t=g+1; t--; )
  90.         if (0 <= r - (1<<t) && d[n*t+r-(1<<t)] < v)
  91.         r -= 1 << t;
  92.     return r? r-1: n;
  93.     }
  94. };
  95.  
  96. typedef unsigned long long ULL;
  97. ULL gcd(ULL x, ULL y) {
  98.     while (1) {
  99.     if (x) y %= x; else return y;
  100.     if (y) x %= y; else return x;
  101.     }
  102. }
  103.  
  104. int N;
  105. int A[50011];
  106.  
  107. LL sums[50011];
  108. ULL G[17][50011];
  109.  
  110. ULL gcdx(int L, int R) {
  111.     int t = __lg(R - L);
  112.     return gcd(G[t][L], G[t][R - (1<<t)]);
  113. }
  114.  
  115. void MAIN() {
  116.     scanf("%d", &N);
  117.     REP (i, N) scanf("%d", A+i);
  118.  
  119.     REP (i, N) {
  120.     G[0][i] = abs(A[i]);
  121.     sums[i+1] = sums[i] + A[i];
  122.     }
  123.  
  124.     IRXQ<int> M(A, A+N);
  125.     IRXQ<LL> S(sums, sums+N+1);
  126.  
  127.     REP (t, 16) {
  128.     REP (i, N) {
  129.         int s = i + (1<<t);
  130.         if (s < N) {
  131.         G[t+1][i] = gcd(G[t][i], G[t][s]);
  132.         }
  133.     }
  134.     }
  135.  
  136.     LL ans = 0;
  137.  
  138.     REP (i, N) if (A[i] > 0) {
  139.     int pos = i;
  140.     while (1) {
  141.         int lo = pos+1, hi = N+1;
  142.         ULL g = gcdx(i, lo);
  143.         while (hi - lo > 1) {
  144.         int mid = (lo + hi) / 2;
  145.         if (gcdx(i, mid) == g) lo = mid;
  146.         else hi = mid;
  147.         }
  148.  
  149.         // [i, lo)
  150.         // [pos, lo)
  151.         int idx = S.max_i(pos+1, lo+1);
  152.         int ma = M.max_v(i, idx);
  153.         LL s = sums[idx] - sums[i];
  154.         amax(ans, (LL)g * (s - ma));
  155.  
  156.         if (lo == N) break;
  157.         pos = lo;
  158.     }
  159.     }
  160.  
  161.     printf("%lld\n", ans);
  162. }
  163.  
  164. int main() {
  165.     int TC = 1;
  166. //    scanf("%d", &TC);
  167.     REP (tc, TC) MAIN();
  168.     return 0;
  169. }
RAW Paste Data