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. #define MAXN 100005
  7. #define MAXLOGN 25
  8. int M[MAXN][MAXLOGN];
  9. int MA[MAXN][MAXLOGN];
  10. int A[1000005];
  11. void increase_stack_depth()			// works on codechef
  12. {
  13. 	rlimit R;
  14. 	getrlimit(RLIMIT_STACK, &R);
  15. 	R.rlim_cur = R.rlim_max;
  16. 	setrlimit(RLIMIT_STACK, &R);
  17. }
  18. void Compute_ST(int N){
  19.     int i,j;
  20.     for(i=0;i<N;i++) {
  21.         M[i][0]=i;
  22.         MA[i][0]=i;
  23.     }
  24.     for(j=1; (1<<j) <= N ;j++){
  25.         for(i=0;i+(1<<(j-1))<N;i++){
  26.             if(A[M[i][j-1]]<=A[M[i+(1<<(j-1))][j-1]])
  27.                 M[i][j]=M[i][j-1];
  28.             else
  29.                 M[i][j]=M[i+(1<<(j-1))][j-1];
  30.  
  31.             if(A[MA[i][j-1]]>=A[MA[i+(1<<(j-1))][j-1]])
  32.                 MA[i][j]=MA[i][j-1];
  33.             else
  34.                 MA[i][j]=MA[i+(1<<(j-1))][j-1];
  35.         }
  36.     }
  37. }
  38. pair <int, int> RMQ(int s,int e){
  39.     int k=e-s;
  40.     pair <int, int> ret;
  41.     k=31-__builtin_clz(k+1); // k = log(e-s+1)
  42.     if(A[M[s][k]]<=A[M[e-(1<<k)+1][k]])
  43.         ret.second = A[M[s][k]];
  44.     else
  45.         ret.second = A[M[e-(1<<k)+1][k]];
  46.  
  47.     if(A[MA[s][k]]>=A[MA[e-(1<<k)+1][k]])
  48.         ret.first = A[MA[s][k]];
  49.     else
  50.         ret.first = A[MA[e-(1<<k)+1][k]];
  51.  
  52.     return ret;
  53. }
  54. int length[107];
  55. long long int dp[(1 << 21) + 1];
  56. int n;
  57. int p = 0;
  58. long long int func (int mask, int len) {
  59.    if (mask == ((1 << p) - 1)) {
  60.         return 0;
  61.     }
  62.     long long int poppy = 0;
  63.     pair <int, int> temp;
  64.     for (int i = 0 ; i < p; i++) {
  65.         int vv = (1 << i);
  66.         if ((mask & (vv)) == 0) {
  67.             temp = RMQ(len, len + length[i] - 1);
  68.             if (dp[1 << (mask | (vv))] != -1 ){
  69.                 poppy = max(poppy, (length[i] *(temp.first - temp.second)) + dp[1 << (mask | (vv))]);
  70.             } else {
  71.                 poppy = max(poppy , (length[i] *(temp.first - temp.second)) + func ((mask | (vv)), len + length[i]) );
  72.             }
  73.         }
  74.     }
  75.     dp[mask] = poppy;
  76.     return poppy;
  77. }
  78.  
  79.  
  80. int main()
  81. {
  82.     increase_stack_depth();
  83.     int q,a,b, v, k;
  84.     scanf("%d", &n);
  85.     for (int i = 0 ; i  < n; i++) {
  86.         scanf("%d", &A[i]);
  87.     }
  88.     Compute_ST(n);
  89.     memset(dp , -1, sizeof(dp));
  90.     scanf("%d", &k);
  91.     int temp;
  92.     for (int i = 0 ; i < k ; i++) {
  93.         scanf("%d", &temp);
  94.         if( temp > 0) {
  95.             length[p++] = temp;
  96.         }
  97.     }
  98.     printf("%lld\n", func(0,0));
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 42968KB
comments (?)
stdin
copy 
9
2 6 3 1 8 4 3 5 6
4
2 3 2 2
stdout
copy 
33
https://ideone.com/Lj6VXf
language:
C++ (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!