fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <sys/resource.h>
  3. #include <limits.h>
  4. #pragma comment(linker, "/STACK: 2000000")
  5. using namespace std;
  6. struct SegmentTreeNode {
  7.     pair <int,int> max_min;
  8.  
  9.     void assignLeaf(int value) {
  10.         max_min = make_pair(value, value);
  11.     }
  12.      void merge (SegmentTreeNode& left, SegmentTreeNode& right) {
  13.          max_min = make_pair(max(left.max_min.first, right.max_min.first), min(left.max_min.second, right.max_min.second));
  14.      }
  15.      pair <int,int> getValue() {
  16.          return max_min;
  17.      }
  18. };
  19. void increase_stack_depth()			// works on codechef
  20. {
  21. 	rlimit R;
  22. 	getrlimit(RLIMIT_STACK, &R);
  23. 	R.rlim_cur = R.rlim_max;
  24. 	setrlimit(RLIMIT_STACK, &R);
  25. }
  26. template<class T, class V>
  27. class SegmentTree {
  28. 	SegmentTreeNode* nodes;
  29. 	int N;
  30.  
  31. public:
  32. 	SegmentTree(T arr[], int N) {
  33. 		this->N = N;
  34. 		nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
  35. 		buildTree(arr, 1, 0, N-1);
  36. 	}
  37.  
  38. 	~SegmentTree() {
  39. 		delete[] nodes;
  40. 	}
  41.  
  42. 	V getValue(int lo, int hi) {
  43. 		SegmentTreeNode result = getValue(1, 0, N-1, lo, hi);
  44. 		return result.getValue();
  45. 	}
  46.  
  47. 	void update(int index, T value) {
  48. 		update(1, 0, N-1, index, value);
  49. 	}
  50.  
  51. private:
  52. 	void buildTree(T arr[], int stIndex, int lo, int hi) {
  53. 		if (lo == hi) {
  54. 			nodes[stIndex].assignLeaf(arr[lo]);
  55. 			return;
  56. 		}
  57.  
  58. 		int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  59. 		buildTree(arr, left, lo, mid);
  60. 		buildTree(arr, right, mid + 1, hi);
  61. 		nodes[stIndex].merge(nodes[left], nodes[right]);
  62. 	}
  63.  
  64. 	SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi) {
  65. 		if (left == lo && right == hi)
  66. 			return nodes[stIndex];
  67.  
  68. 		int mid = (left + right) / 2;
  69. 		if (lo > mid)
  70. 			return getValue(2*stIndex+1, mid+1, right, lo, hi);
  71. 		if (hi <= mid)
  72. 			return getValue(2*stIndex, left, mid, lo, hi);
  73.  
  74. 		SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
  75. 		SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
  76. 		SegmentTreeNode result;
  77. 		result.merge(leftResult, rightResult);
  78. 		return result;
  79. 	}
  80.  
  81. 	int getSegmentTreeSize(int N) {
  82. 		int size = 1;
  83. 		for (; size < N; size <<= 1);
  84. 		return size << 1;
  85. 	}
  86.  
  87. 	void update(int stIndex, int lo, int hi, int index, T value) {
  88. 		if (lo == hi) {
  89. 			nodes[stIndex].assignLeaf(value);
  90. 			return;
  91. 		}
  92.  
  93. 		int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
  94. 		if (index <= mid)
  95. 			update(left, lo, mid, index, value);
  96. 		else
  97. 			update(right, mid+1, hi, index, value);
  98.  
  99. 		nodes[stIndex].merge(nodes[left], nodes[right]);
  100. 	}
  101. };
  102. int input[1000005];
  103. int length[10000007];
  104. long int dp[(1 << 22) + 1];
  105. int n;
  106. int p = 0;
  107. SegmentTree <int , pair<int, int> > *ans;
  108. long int func (int mask, int len) {
  109.     if (mask == (1 << p) - 1) {
  110.         return 0;
  111.     }
  112.     if(dp[ mask] != -1) {
  113.         return dp[mask];
  114.     }
  115.     long int poppy = 0;
  116.     pair <int, int> temp;
  117.     for (int i = 0 ; i < p; i++) {
  118.         if ((mask & (1 << i)) == 0) {
  119.             temp = (*ans).getValue(len, len + length[i] - 1);
  120.             poppy = max(poppy , (length[i] *(temp.first - temp.second)) + func ((mask | (1 << i)), len + length[i]) );
  121.         }
  122.     }
  123.     dp[mask] = poppy;
  124.     return poppy;
  125. }
  126.  
  127.  
  128. int main() 
  129. {
  130.  
  131.     increase_stack_depth();
  132.     int q,a,b, v, k;
  133.     scanf("%d", &n);
  134.     for (int i = 0 ; i  < n; i++) {
  135.         scanf("%d", &input[i]);
  136.     }
  137.     ans = new SegmentTree < int, pair <int, int> > (input, n);
  138.     memset(dp , -1, sizeof(dp));
  139.     scanf("%d", &k);
  140.     int temp;
  141.     for (int i = 0 ; i < k ; i++) {
  142.         scanf("%d", &temp);
  143.         if( temp > 0) {
  144.             length[p++] = temp;
  145.         }
  146.     }
  147.     printf("%ld\n", func(0,0));
  148.     return 0;
  149. }
Runtime error #stdin #stdout 0.12s 199104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/n7PfoO
language:
C++14 (gcc 8.3)
created:
9 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!