题目链接
AtCoder:https://arc072.contest.atcoder.jp/tasks/arc072_c
洛谷:https://www.luogu.org/problemnew/show/AT2401
Solution
很巧妙的题。
我们考虑从后往前推,设\(b[i]\)表示\(i\sim n\)一定可以到达目的地的点的\(mex-1\),也就是\(0\sim b[i]\)都必然可以到目的地,假设其他的所有点都可以通过某种方式修改\(a[i-1]\)使之不可行。
设当前\(dp\)到\(i\),\(i\)的移动距离为\(a[i]\),画个图可以知道\((b[i+1],\lfloor\frac{a[i]}{2}\rfloor]\)这个区间是不能到达目的地的,其余所有在\([0,b[i+1]+a[i]]\)的位置都可以到。
所以我们只需要判一下上面那个区间存不存在就好了,然后直接转移\(b[i]\),复杂度\(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
const int maxn = 5e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
int n,q,d,a[maxn],b[maxn],dis[maxn];
signed main() {
read(n),read(d);dis[0]=d;
for(int i=1;i<=n;i++) read(a[i]),dis[i]=min(dis[i-1],abs(dis[i-1]-a[i]));
for(int i=n;i;i--) b[i]=b[i+1]+a[i]*(a[i]/2<=b[i+1]);read(q);
for(int i=1,x;i<=q;i++) read(x),puts(dis[x-1]>b[x+1]?"YES":"NO");
return 0;
}