fork download 
  1. /* 
  2.    Problem Name : 8284. Weighted Sum
  3.    spoj
  4. */
  5. #include<bits/stdc++.h>
  6. #ifdef ONLINE_JUDGE
  7.  #define gc getchar_unlocked
  8. #else
  9.  #define gc getchar
  10. #endif
  11. using namespace std;
  12.  
  13. #define MAX 1000005
  14. long long int a[MAX],b[MAX],w[MAX],dp[MAX];
  15.  
  16. void fs(long long int &x)
  17. {
  18.     register int c = gc();
  19.     x = 0;
  20.     int neg = 0;
  21.     for(;((c<48 || c>57) && c != '-');c = gc());
  22.     if(c=='-') {neg=1;c=gc();}
  23.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  24.     if(neg) x=-x;
  25. }
  26. int main()
  27. {
  28.     long long int t,n;
  29.     fs(t);
  30.  
  31.     while(t--)
  32.     {
  33.         memset(dp,0,sizeof(dp));
  34.         fs(n);
  35.  
  36.         for(int i=0;i<n;i++)
  37.         {
  38.             fs(a[i]);
  39.             if(i!=0)
  40.             {
  41.                 b[i] = b[i-1] + (i+1)*a[i];
  42.             }
  43.             else
  44.                 b[0] = a[0];
  45.         }
  46.         w[0] = 1;
  47.         dp[0] = a[0];
  48.  
  49.         for(int i=1;i<n;i++)
  50.         {
  51.             dp[i] = max(dp[i-1]+(2*a[i]),b[i]);
  52.             dp[i] = max(dp[i],((w[i-1]+1)*a[i])+dp[i-1]);
  53.  
  54.             if(dp[i]==(w[i-1]+1)*a[i])
  55.                 w[i] = w[i-1] + 1;
  56.             else if(dp[i]==b[i])
  57.                 w[i] = i+1;
  58.             else
  59.                 w[i] = 2;
  60.         }
  61.         printf("%lld\n",dp[n-1]);
  62.     }
  63.     return 0;
  64. }
  65.  
  66.  
Success #stdin #stdout 0s 34552KB
comments (?)
stdin 
1 
4 
1 
2 
3 
-4
stdout 
6
https://ideone.com/XKDKGk
language:
C++ (gcc 8.3)
created:
9 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!