fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define mii map<int,int>
  5. #define mll map<ll,ll>
  6. #define pii pair<int,int>
  7. #define pli pair<ll,int>
  8. #define pll pair<ll,ll>
  9. #define fi first
  10. #define se second
  11. using namespace std;
  12. int t, n, a[500005];
  13. ll pf[500005], dp, st[2000005], res[500005];
  14. vector<ll> nen;
  15. int gpos(ll x) {
  16.     return lower_bound(nen.begin(),nen.end(),x)-nen.begin();
  17. }
  18. void upd(int id, int l, int r, int pos, int rpos) {
  19.     if (l>pos || r<pos) return;
  20.     if (l==r) {
  21.         st[id]=max(st[id],dp-rpos);
  22.         return;
  23.     }
  24.     int mid=(l+r)/2;
  25.     upd(id*2,l,mid,pos,rpos);
  26.     upd(id*2+1,mid+1,r,pos,rpos);
  27.     st[id]=max(st[id*2],st[id*2+1]);
  28.     return;
  29. }
  30. ll gans(int id, int l, int r, int u, int v) {
  31.     if (l>v || r<u) return -1e9;
  32.     if (l>=u && r<=v) return st[id];
  33.     int mid=(l+r)/2;
  34.     return max(gans(id*2,l,mid,u,v),gans(id*2+1,mid+1,r,u,v));
  35. }
  36. int main() {
  37.     ios_base::sync_with_stdio(false);
  38.     cin.tie(nullptr); cout.tie(nullptr);
  39.     cin>>t;
  40.     while (t--) {
  41.         nen.clear();
  42.         cin>>n;
  43.         for (int i=0; i<=4*(n+1); i++) {
  44.             st[i]=-1e9;
  45.         }
  46.         pf[0]=0;
  47.         nen.push_back(0);
  48.         res[0]=-1e9;
  49.         for (int i=1; i<=n; i++) {
  50.             cin>>a[i];
  51.             pf[i]=pf[i-1]+a[i];
  52.             nen.push_back(pf[i]);
  53.             res[i]=-1e9;
  54.         }
  55.         sort(nen.begin(),nen.end());
  56.         nen.erase(unique(nen.begin(),nen.end()),nen.end());
  57.         for (int i=0; i<=n; i++) {
  58.             pf[i]=gpos(pf[i]);
  59.         }
  60.         dp=0;
  61.         upd(1,0,n,pf[0],0);
  62.         res[pf[0]]=0;
  63.         for (int i=1; i<=n; i++) {
  64.             dp=max({gans(1,0,n,0,pf[i]-1)+i,res[pf[i]],dp-1});
  65.             res[pf[i]]=max(res[pf[i]],dp);
  66.             upd(1,0,n,pf[i],i);
  67.         }
  68.         cout<<dp<<endl;
  69.     }
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iqz5eD
language:
C++14 (gcc 8.3)
created:
1 day 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!