Submission #1439796

---

Source Code Expand

/*
	  - - 
这次如果Ac我吃土 
*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define pb push_back
#define mp make_pair
#define INF 9999999
#define LINF 9999999999999999
#define SINF "%"
#define uint unsigned int
#define msn(a,v) memset(a,v,sizeof(a))
#define ms(a) msn(a,0)
#define NONE -1
#define ll long long
#define ull unsigned ll
#define uchar unsigned char
#define sint short int
#define usint unsigned sint
#define xsize(a) sizeof(a)/1024/1024
#define fr(aaaaa,bbbbb) for(aaaaa = 1;aaaaa <= bbbbb;aaaaa++)
#define frr(aaaaa,bbbbb,ccccc) for(aaaaa = ccccc;aaaaa <= bbbbb;aaaaa++)
using namespace std;
#define MAXN 1000
#define MOD 1000000007

ll n,a,b;
ll data[MAXN];
ll dp[MAXN]; 

int main(){
	//freopen("C.txt","r",stdin);
	data[0] = -1000000000000;
	
	cin >> n >> a >> b;
	for(int i = 1;i <= n;i++)
		cin >> data[i];
	
	ms(dp);
	dp[0] = 1;
	ll now = 0;
	ll lastpos = 0;
	for(int i = 1;i <= n;i++){
		//在 (0,i] 之间找到最小的lastpos,使data[i]和data[lastpos]不可以被同时放到Y中 
		for(;lastpos < i  &&  data[i] - data[lastpos] >= b;lastpos++){
			now += dp[lastpos];
			if(now >= MOD) now -= MOD;
		}
		dp[i] = now;
		if(data[i] - data[i-1] < a){
			now = 0;
			lastpos = i-1;
		}
	}
	
	for(int i = lastpos;i <= n;i++){
		now += dp[i];
		if(now >= MOD) now -= MOD;
	}
	
	cout << now << endl;
	
	return 0;
}

Submission Info

Judge Result