fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lli long long
  3. #define pll pair<lli,lli>
  4.  
  5. using namespace std;
  6.  
  7. int k;
  8. int n;
  9. lli A[100005];
  10. lli B[22];
  11. bool vis[1<<20];
  12. lli dp[1<<20];
  13. pll F[100005][21];
  14.  
  15. // fast input
  16. template<typename T>
  17. inline void fi(T *a)
  18. {
  19.  register char c=0;
  20.  while (c<33) c=getchar_unlocked();
  21.  *a=0;
  22.  int tmp = 0;
  23.  while (c>33)
  24.  {
  25.      if ( c == 45 ) tmp = 1;
  26.      else *a=*a*10+c-'0';
  27.      c=getchar_unlocked();
  28.  }
  29.  if ( tmp == 1 ) *a = 0-(*a);
  30. }
  31.  
  32. void pre()
  33. {
  34.     for ( int i = 0; i < n; i++ ) {
  35.         F[i][0].first = F[i][0].second = A[i];
  36.     }
  37.     int kk = (int)log2(n);
  38.     for ( int i = 1; i <= kk; i++ ) {
  39.         for ( int j = 0; j + (1<<(i-1)) < n; j++ ) {
  40.             F[j][i].first = max(F[j][i-1].first, F[j+(1<<(i-1))][i-1].first);
  41.             F[j][i].second = min(F[j][i-1].second, F[j+(1<<(i-1))][i-1].second);
  42.         }
  43.     }
  44. }
  45.  
  46. pll get(int a, int b)
  47. {
  48.     int kk = (int)log2(b-a+1);
  49.     pll ans;
  50.     ans.first = max(F[a][kk].first, F[b+1-(1<<kk)][kk].first);
  51.     ans.second = min(F[a][kk].second, F[b+1-(1<<kk)][kk].second);
  52.     return ans;
  53. }
  54.  
  55. lli f(int mask, int len)
  56. {
  57. 	if ( mask == ((1<<k)-1) ) return 0LL;
  58. 	if ( vis[mask] ) return dp[mask];
  59. 	vis[mask] = true;
  60. 	lli ans = 0;
  61. 	for ( int i = 0; i < k; i++ ) {
  62. 		if ( mask&(1<<i) ) continue;
  63. 		pll tt = get(len, len + B[i]-1);
  64. 		ans = max(ans, (tt.first - tt.second)*B[i] + f(mask|(1<<i), len + B[i]));
  65. 	}
  66. 	dp[mask] = ans;
  67. 	return ans;
  68. }
  69.  
  70. int main()
  71. {
  72. 	fi(&n);
  73. 	for ( int i = 0; i < n; i++ ) fi(&A[i]);
  74. 	pre();
  75. 	fi(&k);
  76. 	for ( int i = 0; i < k; i++ ) fi(&B[i]);
  77. 	lli ans = f(0,0);
  78. 	printf("%lld\n", ans);
  79. 	return 0;
  80. }
  81.  
Success #stdin #stdout 0.03s 45504KB
comments (?)
stdin
copy 
9
2 6 3 1 8 4 3 5 6
4
2 3 2 2
stdout
copy 
33
https://ideone.com/E1OyvF
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years 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!