Submission #19,816

19816

2025-12-24 11:06:23

cpp17

Accepted 100/100

2.595s

61236 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;
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
	subtask1	0/0	1	Accepted	1ms	316 KiB
	subtask2	5/5
			2	Accepted	13ms	428 KiB
			3	Accepted	17ms	316 KiB
			4	Accepted	50ms	484 KiB
			5	Accepted	82ms	488 KiB
			6	Accepted	83ms	316 KiB
			7	Accepted	158ms	316 KiB
			8	Accepted	453ms	508 KiB
			9	Accepted	1.2s	684 KiB
			10	Accepted	1.197s	684 KiB
			11	Accepted	1.189s	704 KiB
			12	Accepted	1.169s	744 KiB
			13	Accepted	1.138s	784 KiB
	subtask3	7/7
			14	Accepted	13ms	508 KiB
			15	Accepted	41ms	440 KiB
			16	Accepted	314ms	564 KiB
			17	Accepted	851ms	712 KiB
			18	Accepted	1.231s	832 KiB
			19	Accepted	1.238s	1556 KiB
			20	Accepted	1.226s	3380 KiB
			21	Accepted	1.23s	3380 KiB
			22	Accepted	1.238s	3300 KiB
			23	Accepted	1.248s	3380 KiB
			24	Accepted	1.246s	3256 KiB
			25	Accepted	1.254s	3716 KiB
			26	Accepted	1.273s	3736 KiB
	subtask4	13/13
			27	Accepted	13ms	508 KiB
			28	Accepted	41ms	440 KiB
			29	Accepted	314ms	564 KiB
			30	Accepted	851ms	712 KiB
			31	Accepted	1.231s	832 KiB
			32	Accepted	1.238s	1556 KiB
			33	Accepted	1.226s	3380 KiB
			34	Accepted	1.23s	3380 KiB
			35	Accepted	1.238s	3300 KiB
			36	Accepted	1.248s	3380 KiB
			37	Accepted	1.246s	3256 KiB
			38	Accepted	1.254s	3716 KiB
			39	Accepted	1.273s	3736 KiB
			40	Accepted	13ms	508 KiB
			41	Accepted	39ms	508 KiB
			42	Accepted	319ms	564 KiB
			43	Accepted	816ms	732 KiB
			44	Accepted	1.228s	832 KiB
			45	Accepted	1.24s	1396 KiB
			46	Accepted	1.243s	3636 KiB
			47	Accepted	1.21s	3652 KiB
			48	Accepted	1.213s	3052 KiB
			49	Accepted	1.261s	3704 KiB
			50	Accepted	1.23s	3528 KiB
			51	Accepted	1.274s	3892 KiB
			52	Accepted	1.217s	3636 KiB
	subtask5	19/19
			53	Accepted	13ms	428 KiB
			54	Accepted	17ms	316 KiB
			55	Accepted	50ms	484 KiB
			56	Accepted	82ms	488 KiB
			57	Accepted	83ms	316 KiB
			58	Accepted	158ms	316 KiB
			59	Accepted	453ms	508 KiB
			60	Accepted	1.2s	684 KiB
			61	Accepted	1.197s	684 KiB
			62	Accepted	1.189s	704 KiB
			63	Accepted	1.169s	744 KiB
			64	Accepted	1.138s	784 KiB
			65	Accepted	13ms	508 KiB
			66	Accepted	41ms	440 KiB
			67	Accepted	314ms	564 KiB
			68	Accepted	851ms	712 KiB
			69	Accepted	1.231s	832 KiB
			70	Accepted	1.238s	1556 KiB
			71	Accepted	1.226s	3380 KiB
			72	Accepted	1.23s	3380 KiB
			73	Accepted	1.238s	3300 KiB
			74	Accepted	1.248s	3380 KiB
			75	Accepted	1.246s	3256 KiB
			76	Accepted	1.254s	3716 KiB
			77	Accepted	1.273s	3736 KiB
			78	Accepted	13ms	508 KiB
			79	Accepted	39ms	508 KiB
			80	Accepted	319ms	564 KiB
			81	Accepted	816ms	732 KiB
			82	Accepted	1.228s	832 KiB
			83	Accepted	1.24s	1396 KiB
			84	Accepted	1.243s	3636 KiB
			85	Accepted	1.21s	3652 KiB
			86	Accepted	1.213s	3052 KiB
			87	Accepted	1.261s	3704 KiB
			88	Accepted	1.23s	3528 KiB
			89	Accepted	1.274s	3892 KiB
			90	Accepted	1.217s	3636 KiB
			91	Accepted	13ms	508 KiB
			92	Accepted	41ms	316 KiB
			93	Accepted	300ms	524 KiB
			94	Accepted	834ms	564 KiB
			95	Accepted	1.148s	828 KiB
			96	Accepted	1.156s	1332 KiB
			97	Accepted	1.24s	3892 KiB
			98	Accepted	1.197s	3356 KiB
			99	Accepted	1.151s	3336 KiB
			100	Accepted	1.041s	3860 KiB
			101	Accepted	1.197s	3632 KiB
			102	Accepted	1.264s	3380 KiB
			103	Accepted	871ms	3672 KiB
	subtask6	9/9
			104	Accepted	13ms	508 KiB
			105	Accepted	41ms	440 KiB
			106	Accepted	314ms	564 KiB
			107	Accepted	851ms	712 KiB
			108	Accepted	1.231s	832 KiB
			109	Accepted	1.238s	1556 KiB
			110	Accepted	1.226s	3380 KiB
			111	Accepted	1.23s	3380 KiB
			112	Accepted	1.238s	3300 KiB
			113	Accepted	1.248s	3380 KiB
			114	Accepted	1.246s	3256 KiB
			115	Accepted	1.254s	3716 KiB
			116	Accepted	1.273s	3736 KiB
			117	Accepted	13ms	508 KiB
			118	Accepted	41ms	316 KiB
			119	Accepted	312ms	564 KiB
			120	Accepted	852ms	564 KiB
			121	Accepted	1.319s	1052 KiB
			122	Accepted	1.631s	5436 KiB
			123	Accepted	2.5s	61236 KiB
			124	Accepted	1.896s	39988 KiB
			125	Accepted	1.483s	35636 KiB
			126	Accepted	2.382s	57396 KiB
			127	Accepted	1.71s	19264 KiB
			128	Accepted	2.595s	45364 KiB
			129	Accepted	1.554s	40084 KiB
	subtask7	14/14
			130	Accepted	13ms	508 KiB
			131	Accepted	41ms	440 KiB
			132	Accepted	314ms	564 KiB
			133	Accepted	851ms	712 KiB
			134	Accepted	1.231s	832 KiB
			135	Accepted	1.238s	1556 KiB
			136	Accepted	1.226s	3380 KiB
			137	Accepted	1.23s	3380 KiB
			138	Accepted	1.238s	3300 KiB
			139	Accepted	1.248s	3380 KiB
			140	Accepted	1.246s	3256 KiB
			141	Accepted	1.254s	3716 KiB
			142	Accepted	1.273s	3736 KiB
			143	Accepted	13ms	508 KiB
			144	Accepted	39ms	508 KiB
			145	Accepted	319ms	564 KiB
			146	Accepted	816ms	732 KiB
			147	Accepted	1.228s	832 KiB
			148	Accepted	1.24s	1396 KiB
			149	Accepted	1.243s	3636 KiB
			150	Accepted	1.21s	3652 KiB
			151	Accepted	1.213s	3052 KiB
			152	Accepted	1.261s	3704 KiB
			153	Accepted	1.23s	3528 KiB
			154	Accepted	1.274s	3892 KiB
			155	Accepted	1.217s	3636 KiB
			156	Accepted	13ms	508 KiB
			157	Accepted	41ms	316 KiB
			158	Accepted	312ms	564 KiB
			159	Accepted	852ms	564 KiB
			160	Accepted	1.319s	1052 KiB
			161	Accepted	1.631s	5436 KiB
			162	Accepted	2.5s	61236 KiB
			163	Accepted	1.896s	39988 KiB
			164	Accepted	1.483s	35636 KiB
			165	Accepted	2.382s	57396 KiB
			166	Accepted	1.71s	19264 KiB
			167	Accepted	2.595s	45364 KiB
			168	Accepted	1.554s	40084 KiB
			169	Accepted	12ms	316 KiB
			170	Accepted	43ms	500 KiB
			171	Accepted	314ms	564 KiB
			172	Accepted	894ms	564 KiB
			173	Accepted	1.317s	1092 KiB
			174	Accepted	1.633s	5428 KiB
			175	Accepted	1.503s	26796 KiB
			176	Accepted	2.174s	30280 KiB
			177	Accepted	1.453s	17372 KiB
			178	Accepted	1.725s	17464 KiB
			179	Accepted	1.521s	17204 KiB
			180	Accepted	2.387s	57140 KiB
			181	Accepted	2.403s	43060 KiB
	subtask8	33/33
			182	Accepted	2ms	500 KiB
			183	Accepted	13ms	428 KiB
			184	Accepted	17ms	316 KiB
			185	Accepted	50ms	484 KiB
			186	Accepted	82ms	488 KiB
			187	Accepted	83ms	316 KiB
			188	Accepted	158ms	316 KiB
			189	Accepted	453ms	508 KiB
			190	Accepted	1.2s	684 KiB
			191	Accepted	1.197s	684 KiB
			192	Accepted	1.189s	704 KiB
			193	Accepted	1.169s	744 KiB
			194	Accepted	1.138s	784 KiB
			195	Accepted	13ms	508 KiB
			196	Accepted	41ms	440 KiB
			197	Accepted	314ms	564 KiB
			198	Accepted	851ms	712 KiB
			199	Accepted	1.231s	832 KiB
			200	Accepted	1.238s	1556 KiB
			201	Accepted	1.226s	3380 KiB
			202	Accepted	1.23s	3380 KiB
			203	Accepted	1.238s	3300 KiB
			204	Accepted	1.248s	3380 KiB
			205	Accepted	1.246s	3256 KiB
			206	Accepted	1.254s	3716 KiB
			207	Accepted	1.273s	3736 KiB
			208	Accepted	13ms	508 KiB
			209	Accepted	39ms	508 KiB
			210	Accepted	319ms	564 KiB
			211	Accepted	816ms	732 KiB
			212	Accepted	1.228s	832 KiB
			213	Accepted	1.24s	1396 KiB
			214	Accepted	1.243s	3636 KiB
			215	Accepted	1.21s	3652 KiB
			216	Accepted	1.213s	3052 KiB
			217	Accepted	1.261s	3704 KiB
			218	Accepted	1.23s	3528 KiB
			219	Accepted	1.274s	3892 KiB
			220	Accepted	1.217s	3636 KiB
			221	Accepted	13ms	508 KiB
			222	Accepted	41ms	316 KiB
			223	Accepted	300ms	524 KiB
			224	Accepted	834ms	564 KiB
			225	Accepted	1.148s	828 KiB
			226	Accepted	1.156s	1332 KiB
			227	Accepted	1.24s	3892 KiB
			228	Accepted	1.197s	3356 KiB
			229	Accepted	1.151s	3336 KiB
			230	Accepted	1.041s	3860 KiB
			231	Accepted	1.197s	3632 KiB
			232	Accepted	1.264s	3380 KiB
			233	Accepted	871ms	3672 KiB
			234	Accepted	13ms	508 KiB
			235	Accepted	41ms	316 KiB
			236	Accepted	312ms	564 KiB
			237	Accepted	852ms	564 KiB
			238	Accepted	1.319s	1052 KiB
			239	Accepted	1.631s	5436 KiB
			240	Accepted	2.5s	61236 KiB
			241	Accepted	1.896s	39988 KiB
			242	Accepted	1.483s	35636 KiB
			243	Accepted	2.382s	57396 KiB
			244	Accepted	1.71s	19264 KiB
245	Accepted		2.595s	45364 KiB
246	Accepted		1.554s	40084 KiB
247	Accepted		12ms	316 KiB
248	Accepted		43ms	500 KiB
249	Accepted		314ms	564 KiB
250	Accepted		894ms	564 KiB
251	Accepted		1.317s	1092 KiB
252	Accepted		1.633s	5428 KiB
253	Accepted		1.503s	26796 KiB
254	Accepted		2.174s	30280 KiB
255	Accepted		1.453s	17372 KiB
256	Accepted		1.725s	17464 KiB
257	Accepted		1.521s	17204 KiB
258	Accepted		2.387s	57140 KiB
259	Accepted		2.403s	43060 KiB
260	Accepted		12ms	316 KiB
261	Accepted		41ms	448 KiB
262	Accepted		310ms	564 KiB
263	Accepted		828ms	608 KiB
264	Accepted		1.225s	1120 KiB
265	Accepted		1.34s	5172 KiB
266	Accepted		1.804s	29420 KiB
267	Accepted		1.154s	31684 KiB
268	Accepted		2.007s	43572 KiB
269	Accepted		1.539s	33588 KiB
270	Accepted		2.095s	51764 KiB
271	Accepted		2.463s	51828 KiB
272	Accepted		1.633s	37608 KiB