fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 5;
  5. int dp[N][2];
  6.  
  7. bool check(int i, bool flip, vector<int>& a, vector<int>& b, int n, int m) {
  8.  
  9. int val = a[i];
  10. if (flip) val = b[0] - val;
  11.  
  12. if (i == n - 1) {
  13. return true;
  14. }
  15.  
  16. if (dp[i][flip] != -1) return dp[i][flip];
  17.  
  18. return dp[i][flip] = (a[i + 1] >= val && check(i + 1, false, a, b, n, m))
  19. || (b[0] - a[i + 1] >= val && check(i + 1, true, a, b, n, m));
  20. }
  21.  
  22. void solve() {
  23. int n, m;
  24. cin >> n >> m;
  25. vector<int> a(n);
  26. memset(dp, -1, sizeof(dp));
  27. for (int i = 0; i < n; i++) {
  28. cin >> a[i];
  29. }
  30. vector<int> b(m);
  31. cin >> b[0];
  32. if (n == 1) {
  33. cout << "YES" << endl;
  34. return;
  35. }
  36. if (check(0, false, a, b, n, m) || check(0, true, a, b, n, m)) {
  37. cout << "YES" << endl;
  38. } else {
  39. cout << "NO" << endl;
  40. }
  41.  
  42. }
  43.  
  44. int main() {
  45. int t;
  46. cin >> t;
  47. while (t--) solve();
  48. }
Success #stdin #stdout 0.01s 5288KB
stdin
5
1 1
5
9
3 1
1 4 3
3
4 1
1 4 2 5
6
4 1
5 4 10 5
4
3 1
9 8 7
8
stdout
YES
NO
YES
NO
YES