fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define INF 1000000000
  4. #define p20 1048576
  5. #define ll long long
  6.  
  7. ll int n,k,a[100000],l[20];
  8. ll int mx[1000000],mn[1000000],dp[p20];
  9.  
  10. ll int query_max(int l,int r,int x,int y,int i){
  11. 	if (l>r||x>r||y<l) return 0;
  12. 	if (l>=x&&r<=y) return mx[i];
  13. 	int mid = (l+r)>>1;
  14. 	int left = 2*i+1;
  15. 	int right = left+1;
  16. 	return max(query_max(l,mid,x,y,left),query_max(mid+1,r,x,y,right));
  17. }
  18.  
  19. ll int query_min(int l,int r,int x,int y,int i){
  20. 	if (l>r||x>r||y<l) return INF;
  21. 	if (l>=x&&r<=y) return mn[i];
  22. 	int mid = (l+r)>>1;
  23. 	int left = 2*i+1;
  24. 	int right = left+1;
  25. 	return min(query_min(l,mid,x,y,left),query_min(mid+1,r,x,y,right));
  26. }
  27.  
  28. ll int return_val(int l,int r){
  29. 	if (l>r) return 0;
  30. 	ll int mxm = query_max(0,n-1,l,r,0);
  31. 	ll int mnm = query_min(0,n-1,l,r,0);
  32. 	return mxm-mnm;
  33. }
  34.  
  35. int buildtree(int l,int r,int i){
  36. 	if (l>r) return 0;
  37. 	if (l==r){
  38. 		mx[i] = mn[i] = a[l];
  39. 		return 0;
  40. 	}
  41. 	int mid = (l+r)>>1;
  42. 	int left = 2*i+1;
  43. 	int right = left+1;
  44. 	buildtree(l,mid,left);
  45. 	buildtree(mid+1,r,right);
  46. 	mx[i] = max(mx[left],mx[right]);
  47. 	mn[i] = min(mn[left],mn[right]);
  48. 	return 0;
  49. }
  50.  
  51. int input(){
  52. 	scanf("%lld",&n);
  53. 	for (ll int i=0;i<n;i++) scanf("%lld",&a[i]);
  54. 	scanf("%lld",&k);
  55. 	for (ll int i=0;i<k;i++) scanf("%lld",&l[i]);
  56. 	buildtree(0,n-1,0);
  57. 	return 0;
  58. }
  59.  
  60. ll int func(ll int mask,ll int x){
  61. 	if (mask==(1<<n)-1) return 0LL;
  62. 	if (dp[mask]!=-1){
  63. 		return dp[mask];
  64. 	}
  65. 	ll int m = 0;
  66. 	for (ll int i=0;i<k;i++){
  67. 		if (((mask)&(1<<i))==0){
  68. 			ll int v = return_val(x,x+l[i]-1);
  69. 			m=max(m,func((mask+(1<<i)),x+l[i])+(v*l[i]));
  70. 		}
  71. 	}
  72. 	dp[mask] = m;
  73. 	return m;
  74. }
  75.  
  76. int main(){
  77. 	input();
  78. 	memset(dp,-1,sizeof(dp));
  79. 	printf("%lld\n",func(0,0));
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0s 28064KB
comments (?)
stdin
copy 
9
2 6 3 1 8 4 3 5 6
4
2 3 2 2
stdout
copy 
33
https://ideone.com/5pdDR2
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!