#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1234567;
const ll INF = 2*1e18;
const int inf = 1e9+7;
ll dp[500005];
ll h[500005];
ll b[500005];
int N,P;

bool isOK(int index,ll key){
	if(h[index]>=key)return 1;
	else return 0;
}

int bs(ll key){
	int ok = N+1;
	int ng = -1;
	while(abs(ok-ng)>1){
		int mid = (ok+ng)/2;
		if(isOK(mid,key))ok=mid;
		else ng = mid;
	}
	return ok;
}
int main(void){
	cin >> N >> P;
	for(int i=1;i<=N;i++){
		int a;cin>>a;
		h[i]=h[i-1]+a;
	}
	for(int i=1;i<=N;i++)cout << h[i] <<endl;
	dp[0]=1;
	//h[i]の高さはh[i]-h[i-1];で出せる
	//どの区間まで足せるかを考える
	for(int i=0;i<=N;i++){
		int ng = bs(P+h[i]+1);
		printf("%d から %dまで飛べる\n",i,ng-1);
		dp[i+1]+=dp[i];
		dp[ng]-=dp[i];
	}
	for(int i=1;i<=N;i++){
		dp[i]=dp[i-1]+dp[i];
	}
	cout << dp[N] << endl;
}

• Like
• LINE
• Tweet
• Copy URL