fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string.h>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. const int MAXN = 155000;
  10.  
  11. long long t[MAXN], f[MAXN];
  12. int n;
  13. int a[MAXN], w[MAXN];
  14.  
  15. void Add(int z, long long w)
  16. {
  17. 	z += 1;
  18. 	for (; z < MAXN; z += z & (-z))
  19. 		t[z] = max(t[z], w);
  20. }
  21.  
  22. long long GetMax(int z)
  23. {
  24. 	long long res = 0;  z += 1;
  25. 	for (; z; z -= z & (-z))
  26. 		res = max(res, t[z]);
  27. 	return res;
  28. }
  29.  
  30. long long Work()
  31. {
  32. 	memset(t, 0, sizeof(t));
  33. 	memset(f, 0, sizeof(f));
  34. 	cin >> n;
  35. 	for (int i = 0; i < n; i ++)
  36. 		cin >> a[i];
  37. 	memcpy(w, a, sizeof(a));
  38. 	sort(w, w + n);
  39. 	int m = unique(w, w + n) - w;
  40.  
  41. 	for (int i = 0; i < n; i ++)
  42. 		a[i] = lower_bound(w, w + m, a[i]) - w;
  43.  
  44. 	for (int i = 0; i < n; i ++)
  45. 		cin >> w[i];
  46. 	long long ans = 0;
  47. 	for (int i = 0; i < n; i ++)
  48. 	{
  49. 		f[i] = GetMax(a[i] - 1) + w[i];
  50. 		ans = max(ans, f[i]);
  51. 		Add(a[i], f[i]);
  52. 	}
  53. 	return ans;
  54. }
  55.  
  56. int main()
  57. {
  58. //	freopen("input.txt", "r", stdin);
  59. //	freopen("output.txt", "w", stdout);
  60. 	ios::sync_with_stdio(false);
  61. 	int T;
  62. 	cin >> T;
  63. 	for (int tt = 0; tt < T; tt ++)
  64. 		cout << Work() << endl;
  65.  
  66. 	return 0;
  67. }
  68.  
Success #stdin #stdout 0s 6764KB
comments (?)
stdin
copy 
1
8  
1 2 3 4 1 2 3 4  
10 20 30 40 15 15 15 50
4  
1 2 3 4  
10 20 30 40
stdout
copy 
110
https://ideone.com/rElK2M
language:
C++14 (gcc 8.3)
created:
5 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!