fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. ll helper(vector<int>&a,int k ,bool isMul){
  6. 	ll dp0 = LLONG_MIN/2;
  7. 	ll dp1 = LLONG_MIN/2;
  8. 	ll dp2 = LLONG_MIN/2;
  9.  
  10. 	ll maxi = LLONG_MIN;
  11.  
  12. 	for(int x : a){
  13. 		ll trans = isMul? (ll)x*k : (ll)x/k;
  14. 		ll next2 = max({(ll)x,dp1+x,dp2+x});
  15. 		ll next1 = max({trans,dp0+trans,dp1+trans});
  16. 		ll next0 = max((ll)x,dp0+x);
  17.  
  18. 		dp0 = next0;
  19. 		dp1 = next1;
  20. 		dp2 = next2;
  21.  
  22. 		maxi = max({maxi,dp0,dp1,dp2});
  23. 	}
  24. 	return maxi;
  25. }
  26.  
  27. ll subArr(vector<int>&a,int k){
  28. 	ll mul = helper(a,k,true);
  29. 	ll div = helper(a,k,false);
  30.  
  31. 	return max(mul,div);
  32. }
  33. int main() {
  34.     int n,k ;cin>>n>>k;
  35.     vector<int>a(n);
  36.     for(int i = 0;i<n ;i++){
  37.     	cin>>a[i];
  38.     }
  39.     cout<<subArr(a,k);
  40. 	return 0;
  41. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5 2
1 -2 3 4 -5
stdout
copy 
14
https://ideone.com/LUVFC0
language:
C++ (gcc 8.3)
created:
19 hours 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!