fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<stack>
  7. #include<queue>
  8. #include<string>
  9. #include<iostream>
  10. #include<map>
  11. #include<stdlib.h>
  12. #include<time.h>  
  13. using namespace std;
  14.  
  15. #define sd(a) scanf("%lld",&a)
  16. #define pd(a) printf("%d\n",(a))
  17. #define LL long long
  18. #define F first
  19. #define S second
  20. #define MP make_pair
  21. #define PB push_back
  22. #define mod 1000000007
  23.  
  24. pair<long long,long long> h[500010];
  25.  
  26. long long dp[500010];
  27. long long s[500010];
  28.  
  29. int main()
  30. {
  31. 	long long n,m,i,pos;
  32. 	sd(n);
  33. 	sd(m);
  34. 	for(i=1;i<=n;++i)
  35. 	{
  36. 		sd(h[i].F);
  37. 		h[i].S=i;
  38. 	}
  39. 	h[0]=MP(0,0);
  40. 	for(i=2;i<=n;++i)
  41. 		h[i].F=h[i-1].F+h[i].F;
  42. 	dp[0]=1;
  43. 	s[0]=1;
  44. 	for(i=1;i<=n;++i)
  45. 	{
  46. 		pos=(*(lower_bound(h,h+n+1,MP(h[i].F-m,(long long)-1)))).S;
  47. 		dp[i]=s[i-1];
  48. 		if(pos>0)
  49. 			dp[i]=(dp[i]-s[pos-1]+mod)%mod;
  50. 		s[i]=(s[i-1]+dp[i])%mod;
  51. 	}
  52. 	printf("%lld\n",dp[n]);
  53.  
  54. }
Runtime error #stdin #stdout 0.48s 18312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jnj6zv
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!