fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define LL unsigned long long int
  4. int bts[10000000];
  5. int pop(unsigned x)
  6. {
  7.     x = x - ((x >> 1) & 0x55555555);
  8.     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  9.     x = (x + (x >> 4)) & 0x0F0F0F0F;
  10.     x = x + (x >> 8);
  11.     x = x + (x >> 16);
  12.     return x & 0x0000003F;
  13. }
  14. void init()
  15. {  
  16. 	bts[0]=0;
  17. 	for(int i=1;i<10000000;i++)
  18. 	{
  19. 		bts[i]=bts[i-1]+pop(i);
  20. 	}
  21. }
  22.  
  23. int Lmb(LL n)
  24. {  
  25. 	int bits=0;
  26. 	while(n > 1)
  27. 	{
  28. 		n>>=1;
  29. 		bits+=1;
  30. 	}
  31. 	return bits;
  32. }
  33. LL Total_Bits(LL n)
  34. {  
  35. 	//cout<<"calling total bits"<<" ";
  36. 	if(n==0) return 0;
  37. 	LL m = Lmb(n);
  38. 	if(n==(pow(2,(m+1))-1))
  39. 		return 1LL*(m+1)*pow(2,m);
  40. 	n = n - pow(2,m);
  41. 	return (n+1) + Total_Bits(n) + m*pow(2,(m-1));
  42. }
  43. LL search(LL H, int L, LL n)
  44. {  
  45. 	LL M=0,c=0;
  46. 	while(L<=H)
  47. 	{
  48. 		M=(H+L)/2;
  49. 		if(M < 10000000) c = bts[M];
  50. 		else
  51. 		{c = Total_Bits(M);}
  52. 		if(c==n) 
  53. 		   return M;
  54. 		else if(c < n)
  55. 		     L=M+1;
  56. 		else if(c > M)
  57. 		     H = M-1;
  58. 	}
  59.   return M;
  60. }
  61. #include <bits/stdc++.h>
  62.  
  63. int main() {
  64.     // Write C++ code here
  65.     int n;
  66.     cin>>n;
  67.     vector<int>a(n);
  68.     for(int i=0;i<n;i++){
  69.         int x;
  70.         cin>>x;
  71.         a[i]=x;
  72.     }
  73.     vector<int>dp(n+1);
  74.     dp[0]=a[0];
  75.     int ans=dp[0];
  76.     for(int i=0;i<n;i++){
  77.     	dp[i]=-1;
  78.         for(int j=0;j<i;j++){
  79.             if(dp[j]!=-1){
  80.                 dp[i] = max(dp[i],dp[j]+a[i]);
  81.             }
  82.         }
  83.         ans=max(ans,dp[i]);
  84.     }
  85.     cout<<ans<<endl;
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
4
3 9 6 6
stdout
copy 
3
https://ideone.com/YuAfM9
problem BIT2, based on SPOJ submission 11034498 (C++ 4.3.2), 2014-02-09 15:54:15
language:
C++ (gcc 8.3)
created:
15 days 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!