fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll int
  3. using namespace std;
  4. ll n,ar[1000];
  5. struct trie
  6. {
  7.     trie *bit[2];
  8.     ll R;
  9.     trie()
  10.     {
  11.         bit[0]=bit[1]=NULL;
  12.         R=1e18;
  13.     }
  14. };
  15. trie *root=new trie();
  16. inline void insert(ll val,ll r)
  17. {
  18.     ll now;
  19.     trie *curr=root;
  20.     for(ll i=20;i>=0;i--)
  21.     {
  22.         now=min(1,val&(1<<i));
  23.         if(curr->bit[now]==NULL)
  24.         {
  25.             trie *temp=new trie();
  26.             curr->bit[now]=temp;
  27.             curr=temp;
  28.         }
  29.         else
  30.             curr=curr->bit[now];
  31.         curr->R=min(curr->R,r);
  32.     }
  33. }
  34. inline ll query(ll val,ll l)
  35. {
  36.     ll now,lookfor,ans=0;
  37.     trie *curr=root;
  38.     for(ll i=20;i>=0;i--)
  39.     {
  40.         now=min(1,val&(1<<i));
  41.         lookfor=1^now;
  42.         //try for lookfor
  43.         if(curr->bit[lookfor]!=NULL)
  44.         {
  45.             if(curr->bit[lookfor]->R<l)
  46.             {
  47.                 ans+=(1<<i);
  48.                 curr=curr->bit[lookfor];
  49.                 continue;
  50.             }
  51.         }
  52.         //i could not get lookfor
  53.         //so try for now
  54.         if(curr->bit[now]!=NULL)
  55.         {
  56.             if(curr->bit[now]->R<l)
  57.             {
  58.                 curr=curr->bit[now];
  59.                 continue;
  60.             }
  61.         }
  62.         return 0;
  63.     }
  64.     return ans;
  65. }
  66. int main()
  67. {
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(0);
  70.     cin>>n;
  71.     for(ll i=0;i<n;i++)
  72.         cin>>ar[i];
  73.     ll sum,ans=-1e18;
  74.     for(ll i=0;i<n;i++)
  75.     {
  76.         sum=0;
  77.         for(ll j=i;j<n;j++)
  78.         {
  79.             sum+=ar[j];
  80.             ans=max(ans,query(sum,i));
  81.             insert(sum,j);
  82.         }
  83.     }
  84.     cout<<ans;
  85.     return 0;
  86. }
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-2147483648
https://ideone.com/TA9rsw
language:
C++14 (gcc 8.3)
created:
6 years 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!