比赛 期末考试1 评测结果 AAEWWEEWEE
题目名称 Interactive 最终得分 20
用户昵称 xuyuqing 运行时间 0.691 s
代码语言 C++ 内存使用 4.51 MiB
提交时间 2026-02-08 11:00:18
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

class fastIn {
	private:
	
	char buf [1 << 20];
	char *p1 = buf;
	char *p2 = buf;
	
	inline char getch ();
	
	public:
	
	template <typename NumT>
	void read (NumT &num);
	
	template <typename NumT>
	fastIn& operator >> (NumT &num);
};

inline char fastIn::getch () {
	if (p1 == p2) {
		p1 = buf;
		p2 = buf + fread (buf, 1, 1 << 20, stdin);
		if (p1 == p2) {
			return EOF;
		}
	}
	return *p1++;
}

template <typename NumT>
void fastIn::read (NumT &num) {
	char ch = getch ();
	NumT op = 1;
	num = 0;
	
	while (ch < '0' || '9' < ch) {
		op = ((ch == '-') ? -1 : 1);
		ch = getch ();
	}
	while ('0' <= ch && ch <= '9') {
		num *= 10;
		num += (ch - '0');
		ch = getch ();
	}
	
	num *= op;
}

template <typename NumT>
fastIn& fastIn::operator >> (NumT &num) {
	read (num);
	return *this;
}

fastIn fin;

const int N = 1145;

int n;
long long k;
long long a[N];
long long sum[N];
int lto[N];
int rto[N];
bool flag[N][N];
long long res[N];
int q;

int main () {

	freopen ("tioj_interactive.in", "r", stdin);
	freopen ("tioj_interactive.out", "w", stdout);

	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		fin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		int j = i;
		long long sum = 0;
		while (true) {
			sum += a[j];
			if (sum >= k) {
				rto[i] = j;
				break;
			}
			j++;
			if (j > n) {
				rto[i] = 0;
				break;
			}
		}

		j = i;
		sum = 0;
		while (true) {
			sum += a[j];
			if (sum >= k) {
				lto[i] = j;
				break;
			}
			j--;
			if (j < 1) {
				lto[i] = 0;
				break;
			}
		}

		if (lto[i]) {
			for (int j = 1; j <= lto[i]; j++) {
				flag[j][i] = true;
			}
		}
		if (rto[i]) {
			for (int j = 1; j <= i; j++) {
				flag[j][rto[i]] = true;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			flag[i][j] |= flag[i][j - 1];
			res[j - i + 1] += flag[i][j];
		}
	}

	for (int i = 1; i <= n ;i++) {
		res[i] += res[i - 1];
	}

	fin >> q;
	int que;
	for (int i = 1; i <= q; i++) {
		fin >> que;
		cout << res[que] << endl;
	}
	
	return 0;
}