fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> pii;
  5. typedef vector < int > vi;
  6. typedef long long int int64;
  7. typedef unsigned long long uLL;
  8. #define MEM(a,b) memset(a,(b),sizeof(a))
  9. #define tr(c,it) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
  10. #define present(c,x) ((c).find(x) != (c).end()) 
  11. #define cpresent(c,x) (find(all(c),x) != (c).end())
  12. #define ain(a,n) int ((a)[(n)]); for(int i=0; i<(n); i++) cin>>((a)[i])
  13. #define FOR(i,n) for(int i=0;i<n;i++)
  14. #define FU(i,a,n) for(int i=a;i<=n;i++)
  15. #define FD(i,a,n) for(int i=n;i>=a;i--)
  16. #define GI(n) scanf("%d",&(n))
  17. #define mod 1000000007
  18. #define INF 2100000000
  19. #define MAXN 500007
  20.  
  21. int n;
  22. ll dp[MAXN],h[MAXN],H[MAXN],m;
  23.  
  24. ll solve(int idx){
  25. 	if(idx >= n) return 1;
  26. 	ll ret = dp[idx];
  27. 	if(ret != -1) return ret;
  28. 	ret = 0;
  29. 	for(int i=idx+1;i<=n;i++){
  30. 		if(H[i]-H[idx] <= m){
  31. 			ret += (solve(i));
  32. 		}
  33. 	}
  34. 	dp[idx] = ret;
  35. 	return ret;
  36. }
  37.  
  38. int main(){
  39. 	ios::sync_with_stdio(0);
  40. 	cin.tie(0);
  41. 	MEM(dp,-1);
  42. 	cin>>n>>m;
  43. 	FOR(i,n){
  44. 		cin>>h[i];
  45. 	}
  46. 	FU(i,1,n){
  47. 		H[i] = H[i-1] + h[i-1];
  48. 	//	cout<<H[i]<<endl;
  49. 	}
  50.  
  51. 	cout<<solve(0)<<endl;	
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 14952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/B6AuWQ
language:
C++14 (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!