fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll a[1500];
  5. int main()
  6. {
  7.     int t;
  8.     scanf("%d",&t);
  9.     for(int i=1; i<=t; i++)
  10.     {
  11.         memset(a,0,sizeof a);
  12.         ll ans=0;
  13.         int n;
  14.         scanf("%d",&n);
  15.         for(int j=1; j<=n; j++)
  16.             scanf("%lld",&a[j]);
  17.  
  18.         if(n==1)
  19.         {
  20.             printf("%lld\n",a[1]);
  21.             continue;
  22.         }
  23.  
  24.         int st=1;
  25.         int mark=1;
  26.         while(true)
  27.         {
  28.  
  29.             ll current=a[st];
  30.             ll maxi=a[st];
  31.             mark=st;
  32.             if(st==n)
  33.             {
  34.                 ans+=a[n];
  35.                 break;
  36.             }
  37.             for(int j=st+1; j<=n; j++)
  38.             {
  39.                 current+=a[j];
  40.                 if((current*((j-st)+1))>=maxi && current>0)
  41.                 {
  42.                     mark=j;
  43.                     maxi=current;
  44.                 }
  45.             }
  46.  
  47.             ans+=(maxi*(mark-st+1));
  48.             if(mark==n)
  49.                 break;
  50.             st=mark+1;
  51.         }
  52.         printf("%lld\n",ans);
  53.     }
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0kJEbo
language:
C++ (gcc 8.3)
created:
7 years 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!