```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, k;
ll a[maxn], sum[maxn];
ll tr[maxn << 2], tg[maxn << 2]; //区间加&求最小值,用线段树
void build(int p, int l, int r) {
tg[p] = 0;
if(l == r) {
tr[p] = sum[l];
return;
}
int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
build(ls, l, mid);
build(rs, mid + 1, r);
tr[p] = min(tr[ls], tr[rs]);
return;
}
inline void pushdown(int p, int ls, int rs) {
if(!tg[p]) return;
tg[ls] += tg[p];
tg[rs] += tg[p];
tr[ls] += tg[p];
tr[rs] += tg[p];
tg[p] = 0;
return;
}
ll query(int p, int l, int r, int a, int b) {
if(r < a || l > b) return 1e18;
if(a <= l && r <= b) return tr[p];
int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
pushdown(p, ls, rs);
return min(query(ls, l, mid, a, b), query(rs, mid + 1, r, a, b));
}
void modify(int p, int l, int r, int a, int b, ll v) {
if(r < a || l > b) return;
if(a <= l && r <= b) {
tr[p] += v;
tg[p] += v;
return;
}
int mid = (l + r) >> 1, ls = p << 1, rs = p << 1 | 1;
pushdown(p, ls, rs);
modify(ls, l, mid, a, b, v);
modify(rs, mid + 1, r, a, b, v);
tr[p] = min(tr[ls], tr[rs]);
return;
}
bool ljudge() { //强制往左
fill(sum + 1, sum + n + 1, 0);
sum[1] = a[k];
for(int i = 2; i <= k; ++i) sum[i] = sum[i - 1] + a[k - i + 1];
build(1, 1, k);
if(tr[1] >= 0) return true;
int pos = 1;
for(int i = k + 1; i <= n; ++i) {
if(a[i] < 0) {
while(pos <= k && query(1, 1, k, pos, pos) + a[i] < 0) pos++;
if(pos > k) return false;
modify(1, 1, k, pos, k, a[i]);
}
else
modify(1, 1, k, pos, k, a[i]);
if(tr[1] >= 0) return true;
}
return false;
}
bool rjudge() { //强制往右
fill(sum + 1, sum + n + 1, 0);
sum[1] = a[k];
for(int i = 2; i <= n - k + 1; ++i) sum[i] = sum[i - 1] + a[k + i - 1];
build(1, 1, n - k + 1);
if(tr[1] >= 0) return true;
int pos = 1;
for(int i = k - 1; i > 0; --i) {
if(a[i] < 0) {
while(pos <= n - k + 1 && query(1, 1, n - k + 1, pos, pos) + a[i] < 0) pos++;
if(pos > n - k + 1) return false;
modify(1, 1, n - k + 1, pos, n - k + 1, a[i]);
}
else
modify(1, 1, n - k + 1, pos, n - k + 1, a[i]);
if(tr[1] >= 0) return true;
}
return false;
}
void work() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%lld", a + i);
if(k == 1 || k == n) {
puts("YES");
return;
}
puts(ljudge() || rjudge() ? "YES" : "NO");
return;
}
int main() {
int T;
cin >> T;
while(T--) work();
return 0;
}
```
by Andrewzdm @ 2022-09-26 15:11:31
@[Andrewzdm](/user/286770) Hack
by yszs @ 2022-09-26 15:34:50
@[Andrewzdm](/user/286770)
1
10 7
-20 -999 1000 1 -1 -1 1 -1 2 -1000
by yszs @ 2022-09-26 15:35:14
答案是yes
by yszs @ 2022-09-26 15:35:36
虽然不知道你这个是怎么错的, 但是对于数据:
1
3 1
-1 -1 -1
就能卡掉
by frankly6 @ 2022-09-26 15:41:06
答案是 no
by frankly6 @ 2022-09-26 15:42:23
@[frankly6](/user/223058) 。。。。看题
by yszs @ 2022-09-26 15:42:53
@[frankly6](/user/223058) 保证出生点非负
by yszs @ 2022-09-26 15:43:08
zdm ACM 巨神!
by frankly6 @ 2022-09-26 15:46:39
@[yszs](/user/363980) sorry……
by frankly6 @ 2022-09-26 15:47:02