198162025-12-24 11:06:23ubormaciPapírrepülőcpp17Elfogadva 100/1002.595s61236 KiB
#include <iostream>
#include <algorithm> // for sort, mainly
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint> // for int64_t, int32_t, etc
#include <queue>
#include <stack>
#include <deque>
#include <numeric> // gcd, lcm
#include <fstream>
#include <bitset> // for bitset
#include <iomanip>
#include <cassert> // for set with custom ordering
#include <type_traits> // for set with custom ordering
#include <utility> // for swap, forward, etc
using namespace std;

// #pragma GCC optimize("O2")
// #pragma GCC optimize("O1","O2","O3","Ofa st","unroll-loops")
// #pragma GCC target("sse","sse2","sse3","sse4.1","sse4.2","avx","avx2","fma")

#pragma GCC optimize("Ofast","unroll-loops")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*

notes:

int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string

vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));

{if statement} ? {truth value} : {false value}

#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

std::lcm(ll a, ll b), std::gcd(int a, int b)

cout << fixed << setprecision(n);

set with custom ordering
set<ll, decltype(&cmp)> qu(cmp);

*/

typedef int32_t ll;

const ll maxspeed = 51;

bool query(ll i, ll j, ll speed, vector<vector<vector<bool>>> & dp) {

	return dp[i][j][speed + maxspeed];

}

void settrue(ll i, ll j, ll speed, vector<vector<vector<bool>>> & dp) {
	dp[i][j][speed + maxspeed] = true;
}

void solve() {
	ll m, n, obs;
	cin >> m >> n >> obs;
	
	vector<vector<bool>> wall(n, vector<bool>(m, false));
	vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(m, vector<bool>(2 * maxspeed + 5, false)));

	vector<ll> wallx(obs, 0);
	vector<ll> wallupy(obs, 0);
	vector<ll> walldowny(obs, 0);

	for(ll i = 0; i < obs; i++) {
		cin >> wallx[i];
	}
	for(ll i = 0; i < obs; i++) {
		cin >> walldowny[i];
	}
	for(ll i = 0; i < obs; i++) {
		cin >> wallupy[i];
	}

	for(ll k = 0; k < obs; k++) {

		//cerr << "\nk=" << k;
		//cerr << "\nwallx=" << wallx[k];
		//cerr << "\nwallup=" << wallupy[k];
		//cerr << "\nwalldown=" << walldowny[k];

		ll j = wallx[k];
		
		for(ll i = n-1; i > wallupy[k]; i--) {
			wall[i][j] = true;
		}

		for(ll i = walldowny[k]-1; i >= 0; i--) {
			wall[i][j] = true;
		}
	}

	/*
	for(ll i = n-1; i >= 0; i--) {
		cerr << "\n" << wall[i];
	}
	*/

	ll starty = n / 2;

	settrue(starty, 0, 0, dp);
	settrue(starty, 0, 1, dp);
	settrue(starty, 0, -1, dp);

	for(ll j = 1; j < m; j++) {

		for(ll i = n - 1; i >= 0; i--) {

			// tehat mostani pozicio [i, j]
			// es meg akarjuk nezni, hogy az elozo oszlopban, milyen poziciokrol
			// milyen sebessegekkel tudunk eljutni a mostanira

			if(wall[i][j]) {
				continue;
			}

			for(ll previ = n - 1; previ >= 0; previ--) {

				if(wall[previ][j-1]) {
					continue;
				}

				if(abs(i - previ) > maxspeed) {
					continue;
				}

				bool there = query(previ, j-1, i - previ, dp);

				if(there) {
					settrue(i, j, i - previ, dp);
				}

			}
			
			vector<bool> herenext(2 * maxspeed + 1, false);

			/*
			cerr << "\nfor pos=" << i << ";" << j << "\npossible to enter with: ";
			for(ll sp = -maxspeed; sp <= maxspeed; sp++) {
				if(query(i, j, sp, dp)) {
					cerr << sp << " ";
				}
			}
			*/

			for(ll sp = -maxspeed; sp <= maxspeed; sp++) {

				ll hereind = sp + maxspeed;

				herenext[hereind] = query(i, j, sp, dp);

				if(sp - 1 >= -maxspeed) {
					herenext[hereind] = herenext[hereind] | query(i, j, sp-1, dp);
				}
				if(sp+1 <= maxspeed) {
					herenext[hereind] = herenext[hereind] | query(i, j, sp+1, dp);
				}
			}

			for(ll sp = -maxspeed; sp <= maxspeed; sp++) {
				if(herenext[sp + maxspeed]) {
					settrue(i, j, sp, dp);
				}
			}
		}
	}

	/*
	for(ll j = 0; j < m; j++) {
		for(ll i = n-1; i >= 0; i--) {

			//cerr << "\nfor pos=" << i << ";" << j << "\npossible to leave with: ";
			for(ll sp = -maxspeed; sp <= maxspeed; sp++) {
				if(query(i, j, sp, dp)) {
					cerr << sp << " ";
				}
			}
		}
	}
	*/

	ll j = m - 1;
	for(ll i = n - 1; i >= 0; i--) {
		
		for(ll sp = -maxspeed; sp <= maxspeed; sp++) {
			if(query(i, j, sp, dp)) {
				cout << "YES\n";
				return;
			}
 		}
	}

	cout << "NO\n";
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	ll tests;
	cin >> tests;
	
	for(ll ti = 0; ti < tests; ti++) {
		solve();
	}

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
subtask25/5
2Elfogadva13ms428 KiB
3Elfogadva17ms316 KiB
4Elfogadva50ms484 KiB
5Elfogadva82ms488 KiB
6Elfogadva83ms316 KiB
7Elfogadva158ms316 KiB
8Elfogadva453ms508 KiB
9Elfogadva1.2s684 KiB
10Elfogadva1.197s684 KiB
11Elfogadva1.189s704 KiB
12Elfogadva1.169s744 KiB
13Elfogadva1.138s784 KiB
subtask37/7
14Elfogadva13ms508 KiB
15Elfogadva41ms440 KiB
16Elfogadva314ms564 KiB
17Elfogadva851ms712 KiB
18Elfogadva1.231s832 KiB
19Elfogadva1.238s1556 KiB
20Elfogadva1.226s3380 KiB
21Elfogadva1.23s3380 KiB
22Elfogadva1.238s3300 KiB
23Elfogadva1.248s3380 KiB
24Elfogadva1.246s3256 KiB
25Elfogadva1.254s3716 KiB
26Elfogadva1.273s3736 KiB
subtask413/13
27Elfogadva13ms508 KiB
28Elfogadva41ms440 KiB
29Elfogadva314ms564 KiB
30Elfogadva851ms712 KiB
31Elfogadva1.231s832 KiB
32Elfogadva1.238s1556 KiB
33Elfogadva1.226s3380 KiB
34Elfogadva1.23s3380 KiB
35Elfogadva1.238s3300 KiB
36Elfogadva1.248s3380 KiB
37Elfogadva1.246s3256 KiB
38Elfogadva1.254s3716 KiB
39Elfogadva1.273s3736 KiB
40Elfogadva13ms508 KiB
41Elfogadva39ms508 KiB
42Elfogadva319ms564 KiB
43Elfogadva816ms732 KiB
44Elfogadva1.228s832 KiB
45Elfogadva1.24s1396 KiB
46Elfogadva1.243s3636 KiB
47Elfogadva1.21s3652 KiB
48Elfogadva1.213s3052 KiB
49Elfogadva1.261s3704 KiB
50Elfogadva1.23s3528 KiB
51Elfogadva1.274s3892 KiB
52Elfogadva1.217s3636 KiB
subtask519/19
53Elfogadva13ms428 KiB
54Elfogadva17ms316 KiB
55Elfogadva50ms484 KiB
56Elfogadva82ms488 KiB
57Elfogadva83ms316 KiB
58Elfogadva158ms316 KiB
59Elfogadva453ms508 KiB
60Elfogadva1.2s684 KiB
61Elfogadva1.197s684 KiB
62Elfogadva1.189s704 KiB
63Elfogadva1.169s744 KiB
64Elfogadva1.138s784 KiB
65Elfogadva13ms508 KiB
66Elfogadva41ms440 KiB
67Elfogadva314ms564 KiB
68Elfogadva851ms712 KiB
69Elfogadva1.231s832 KiB
70Elfogadva1.238s1556 KiB
71Elfogadva1.226s3380 KiB
72Elfogadva1.23s3380 KiB
73Elfogadva1.238s3300 KiB
74Elfogadva1.248s3380 KiB
75Elfogadva1.246s3256 KiB
76Elfogadva1.254s3716 KiB
77Elfogadva1.273s3736 KiB
78Elfogadva13ms508 KiB
79Elfogadva39ms508 KiB
80Elfogadva319ms564 KiB
81Elfogadva816ms732 KiB
82Elfogadva1.228s832 KiB
83Elfogadva1.24s1396 KiB
84Elfogadva1.243s3636 KiB
85Elfogadva1.21s3652 KiB
86Elfogadva1.213s3052 KiB
87Elfogadva1.261s3704 KiB
88Elfogadva1.23s3528 KiB
89Elfogadva1.274s3892 KiB
90Elfogadva1.217s3636 KiB
91Elfogadva13ms508 KiB
92Elfogadva41ms316 KiB
93Elfogadva300ms524 KiB
94Elfogadva834ms564 KiB
95Elfogadva1.148s828 KiB
96Elfogadva1.156s1332 KiB
97Elfogadva1.24s3892 KiB
98Elfogadva1.197s3356 KiB
99Elfogadva1.151s3336 KiB
100Elfogadva1.041s3860 KiB
101Elfogadva1.197s3632 KiB
102Elfogadva1.264s3380 KiB
103Elfogadva871ms3672 KiB
subtask69/9
104Elfogadva13ms508 KiB
105Elfogadva41ms440 KiB
106Elfogadva314ms564 KiB
107Elfogadva851ms712 KiB
108Elfogadva1.231s832 KiB
109Elfogadva1.238s1556 KiB
110Elfogadva1.226s3380 KiB
111Elfogadva1.23s3380 KiB
112Elfogadva1.238s3300 KiB
113Elfogadva1.248s3380 KiB
114Elfogadva1.246s3256 KiB
115Elfogadva1.254s3716 KiB
116Elfogadva1.273s3736 KiB
117Elfogadva13ms508 KiB
118Elfogadva41ms316 KiB
119Elfogadva312ms564 KiB
120Elfogadva852ms564 KiB
121Elfogadva1.319s1052 KiB
122Elfogadva1.631s5436 KiB
123Elfogadva2.5s61236 KiB
124Elfogadva1.896s39988 KiB
125Elfogadva1.483s35636 KiB
126Elfogadva2.382s57396 KiB
127Elfogadva1.71s19264 KiB
128Elfogadva2.595s45364 KiB
129Elfogadva1.554s40084 KiB
subtask714/14
130Elfogadva13ms508 KiB
131Elfogadva41ms440 KiB
132Elfogadva314ms564 KiB
133Elfogadva851ms712 KiB
134Elfogadva1.231s832 KiB
135Elfogadva1.238s1556 KiB
136Elfogadva1.226s3380 KiB
137Elfogadva1.23s3380 KiB
138Elfogadva1.238s3300 KiB
139Elfogadva1.248s3380 KiB
140Elfogadva1.246s3256 KiB
141Elfogadva1.254s3716 KiB
142Elfogadva1.273s3736 KiB
143Elfogadva13ms508 KiB
144Elfogadva39ms508 KiB
145Elfogadva319ms564 KiB
146Elfogadva816ms732 KiB
147Elfogadva1.228s832 KiB
148Elfogadva1.24s1396 KiB
149Elfogadva1.243s3636 KiB
150Elfogadva1.21s3652 KiB
151Elfogadva1.213s3052 KiB
152Elfogadva1.261s3704 KiB
153Elfogadva1.23s3528 KiB
154Elfogadva1.274s3892 KiB
155Elfogadva1.217s3636 KiB
156Elfogadva13ms508 KiB
157Elfogadva41ms316 KiB
158Elfogadva312ms564 KiB
159Elfogadva852ms564 KiB
160Elfogadva1.319s1052 KiB
161Elfogadva1.631s5436 KiB
162Elfogadva2.5s61236 KiB
163Elfogadva1.896s39988 KiB
164Elfogadva1.483s35636 KiB
165Elfogadva2.382s57396 KiB
166Elfogadva1.71s19264 KiB
167Elfogadva2.595s45364 KiB
168Elfogadva1.554s40084 KiB
169Elfogadva12ms316 KiB
170Elfogadva43ms500 KiB
171Elfogadva314ms564 KiB
172Elfogadva894ms564 KiB
173Elfogadva1.317s1092 KiB
174Elfogadva1.633s5428 KiB
175Elfogadva1.503s26796 KiB
176Elfogadva2.174s30280 KiB
177Elfogadva1.453s17372 KiB
178Elfogadva1.725s17464 KiB
179Elfogadva1.521s17204 KiB
180Elfogadva2.387s57140 KiB
181Elfogadva2.403s43060 KiB
subtask833/33
182Elfogadva2ms500 KiB
183Elfogadva13ms428 KiB
184Elfogadva17ms316 KiB
185Elfogadva50ms484 KiB
186Elfogadva82ms488 KiB
187Elfogadva83ms316 KiB
188Elfogadva158ms316 KiB
189Elfogadva453ms508 KiB
190Elfogadva1.2s684 KiB
191Elfogadva1.197s684 KiB
192Elfogadva1.189s704 KiB
193Elfogadva1.169s744 KiB
194Elfogadva1.138s784 KiB
195Elfogadva13ms508 KiB
196Elfogadva41ms440 KiB
197Elfogadva314ms564 KiB
198Elfogadva851ms712 KiB
199Elfogadva1.231s832 KiB
200Elfogadva1.238s1556 KiB
201Elfogadva1.226s3380 KiB
202Elfogadva1.23s3380 KiB
203Elfogadva1.238s3300 KiB
204Elfogadva1.248s3380 KiB
205Elfogadva1.246s3256 KiB
206Elfogadva1.254s3716 KiB
207Elfogadva1.273s3736 KiB
208Elfogadva13ms508 KiB
209Elfogadva39ms508 KiB
210Elfogadva319ms564 KiB
211Elfogadva816ms732 KiB
212Elfogadva1.228s832 KiB
213Elfogadva1.24s1396 KiB
214Elfogadva1.243s3636 KiB
215Elfogadva1.21s3652 KiB
216Elfogadva1.213s3052 KiB
217Elfogadva1.261s3704 KiB
218Elfogadva1.23s3528 KiB
219Elfogadva1.274s3892 KiB
220Elfogadva1.217s3636 KiB
221Elfogadva13ms508 KiB
222Elfogadva41ms316 KiB
223Elfogadva300ms524 KiB
224Elfogadva834ms564 KiB
225Elfogadva1.148s828 KiB
226Elfogadva1.156s1332 KiB
227Elfogadva1.24s3892 KiB
228Elfogadva1.197s3356 KiB
229Elfogadva1.151s3336 KiB
230Elfogadva1.041s3860 KiB
231Elfogadva1.197s3632 KiB
232Elfogadva1.264s3380 KiB
233Elfogadva871ms3672 KiB
234Elfogadva13ms508 KiB
235Elfogadva41ms316 KiB
236Elfogadva312ms564 KiB
237Elfogadva852ms564 KiB
238Elfogadva1.319s1052 KiB
239Elfogadva1.631s5436 KiB
240Elfogadva2.5s61236 KiB
241Elfogadva1.896s39988 KiB
242Elfogadva1.483s35636 KiB
243Elfogadva2.382s57396 KiB
244Elfogadva1.71s19264 KiB
245Elfogadva2.595s45364 KiB
246Elfogadva1.554s40084 KiB
247Elfogadva12ms316 KiB
248Elfogadva43ms500 KiB
249Elfogadva314ms564 KiB
250Elfogadva894ms564 KiB
251Elfogadva1.317s1092 KiB
252Elfogadva1.633s5428 KiB
253Elfogadva1.503s26796 KiB
254Elfogadva2.174s30280 KiB
255Elfogadva1.453s17372 KiB
256Elfogadva1.725s17464 KiB
257Elfogadva1.521s17204 KiB
258Elfogadva2.387s57140 KiB
259Elfogadva2.403s43060 KiB
260Elfogadva12ms316 KiB
261Elfogadva41ms448 KiB
262Elfogadva310ms564 KiB
263Elfogadva828ms608 KiB
264Elfogadva1.225s1120 KiB
265Elfogadva1.34s5172 KiB
266Elfogadva1.804s29420 KiB
267Elfogadva1.154s31684 KiB
268Elfogadva2.007s43572 KiB
269Elfogadva1.539s33588 KiB
270Elfogadva2.095s51764 KiB
271Elfogadva2.463s51828 KiB
272Elfogadva1.633s37608 KiB