fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll long long
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 1000001
  13. #define OFFSET 50
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<30)
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q, h, w ;
  21. ll a[MAXN], x[MAXN ], e[MAXN ], s[MAXN ] ;
  22. bool dp[1001][1001][101  ] ;
  23. pair<ll,ll> limit[MAXN ] ;
  24.  
  25. void init() {
  26.     cin >> n >> h >> w ;
  27.     FOR(i, 1, w ) cin >> x[i] ;
  28.     FOR(i, 1, w ) cin >> s[i] ;
  29.     FOR(i, 1, w ) cin >> e[i] ;
  30.     FOR(i , 0 , n ) {
  31.     limit[i] = {0 , h - 1 } ;
  32.     }
  33.     FOR(i, 1, w ) {
  34.         limit[x[i]] = {s[i], e[i] } ;
  35.     }
  36. }
  37.  
  38. void solve() {
  39.     FOR(i, 0, n ) FOR(j, 0, h ) FOR(f, 0, 100 ) dp[i][j][f] = 0 ;
  40.     dp[0][h / 2 ][ 0 + OFFSET ] = true ;
  41.     FOR(i, 0, n - 2 ) {
  42.         FOR(j, 0, h ) FOR (v, -OFFSET, OFFSET ) {
  43.             if(dp[i][j][v + OFFSET ] == 0 ) continue ;
  44.             FOR(dir, -1, 1 ) {
  45.                 ll cur_v = v  + dir ;
  46.                 if(cur_v < -OFFSET || cur_v > OFFSET ) continue ;
  47.                 ll nxt_h = j + cur_v ;
  48.                 if (nxt_h >= 0 && nxt_h < h && limit[i + 1].fi <= nxt_h && nxt_h <= limit[i + 1].se ) dp[i + 1][nxt_h][cur_v + OFFSET] = true;
  49.  
  50.             }
  51.         }
  52.     }
  53.  
  54.     ll ok = false ;
  55.     FOR(j, 0, h ) FOR(g, 0, 100 ) if(dp[n - 1 ][j][g] ) ok = true ;
  56.     cout << (ok ? "YES" : "NO") << el ;
  57. }
  58.  
  59. _ROOT_ {
  60.     // freopen(NAME".inp" , "r" , stdin);
  61.     // freopen(NAME".out" , "w", stdout) ;
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.     int t = 1;
  66.     cin >> t ;
  67.     while(t--) {
  68.         init();
  69.         solve();
  70.     }
  71.     return (0&0);
  72. }
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/OyJki2
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!