fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define st first
  3. #define nd second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define inf 1000000007
  7. #define N 1000005
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. int n, m, a[N], pre[N], fen[N], x[N], dp[N];
  13. map < int , int > h, comp;
  14. map < int , int > :: iterator it;
  15.  
  16. void up(int x, int y){
  17. 	for(; x <= m; x += x&-x)
  18. 		fen[x] = max(fen[x], y);
  19. }
  20.  
  21. int qu(int x){
  22. 	int ans = -inf;
  23. 	for(; x > 0; x -= x&-x)
  24. 		ans = max(ans, fen[x]);
  25. 	return ans;
  26. }
  27.  
  28. int main() {
  29. 	scanf("%d",&n);
  30. 	h[-inf] = h[inf] = h[0] = 1;
  31. 	for(int i = 1; i <= n; i++){
  32. 		scanf("%d",a + i);
  33. 		pre[i] = pre[i - 1] + a[i];
  34. 		h[pre[i]] = 1;
  35. 	}
  36.  
  37. 	for(it = h.begin(); it != h.end(); it++)
  38. 		comp[it->st] = ++m;
  39.  
  40. 	for(int i = 0; i < N; i++)
  41. 		fen[i] = -inf;
  42.  
  43. 	up(comp[0], 0);
  44. 	for(int i = 1; i <= n; i++){
  45. 		dp[i] = qu(comp[pre[i]] - 1) + 1;
  46. 		up(comp[pre[i]], dp[i]);
  47. 	}
  48. 	printf("%d\n", dp[n]);
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 34768KB
comments (?)
stdin
copy 
5
10 -2 -30 40 -1
stdout
copy 
2
https://ideone.com/aEt5sT
language:
C++ (gcc 8.3)
created:
7 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!