牛客-抓捕孔联顺

牛客-抓捕孔联顺 字节跳动C++开发2019编程春招 关键词 动态规划

关键点：
1.使用long long防爆
2.滑动窗口求最大解

#include
#include
using namespace std;

long long C(long long n){
	return n * (n-1) / 2;
}
int main()
{
	long long n, d, count=0;
	cin >> n >> d;
	vector dis(n);
	for(int i = 0, j = 0; i < n; i++){
		cin >> dis[i];
		while(i >= 2 && (dis[i] - dis[j]) > d)
			j++;
		count += C(i-j);
	}
	cout << count % 99997867;
	return 0;
}