C++11(clang++ 3.9) 解法, 执行用时: 425ms, 内存消耗: 8044K, 提交时间: 2019-10-24 20:26:12

# include <iostream>	// NQ
# include <cstdio>
# include <algorithm>

using namespace std;

const int N = 1e6 + 5;
int n, m, k, sum[N];
int q[N], hh, tt;

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &sum[i]);
		sum[i] += sum[i - 1];
	}
	int max_res = -0x3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		if (hh <= tt && i - q[hh] > k)
			hh++;
		max_res = max(max_res, sum[i] - sum[q[hh]]);
		while (hh <= tt && sum[i] <= sum[q[tt]])
			tt--;
		q[++tt] = i;
	}
	while (m--) {
		int x;
		scanf("%d", &x);
		if (max_res >= x)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 416ms, 内存消耗: 20188K, 提交时间: 2019-10-25 22:58:26

#include<cstdio>
#include<algorithm>
using namespace std;
int s[1000005],q[1000005];
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	int head=1,tail=0;
	s[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		s[i]+=s[i-1];
	}
	int maxn=-999999;
	
	for(int i=1;i<=n;i++)       /*构造单调队列来做长度为 k 的滑动窗口*/
	{
		while(head<=tail&&q[tail]-q[head]>k) /*滑动窗口队首进位*/ 
		head++;
		while(head<=tail&&s[i]<s[q[tail]])       /*维护单调递增队列：新进的元素若小于队列尾元素，则队尾舍弃*/
		tail--;
		q[++tail]=i;
		maxn=max(s[i]-s[q[head]],maxn);
		
		    
	}
	while(m--)
	{
		int b;
		scanf("%d",&b);
		maxn>=b?printf("YES\n"):printf("NO\n");
		
	}
	
}