Submission #536661


Source Code Expand

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <cmath>
#ifndef ONLINE_JUDGE
# include <complex>
# include <random>
# include <array>
# include <unordered_map>
# define mkt make_tuple
#endif
#ifdef _LOCAL
# include "local/local.hpp"
#else
# define assert(...) ((void)0)
# define ifdebug if (false)
# define echo(...) ((void)0)
#endif
using namespace std;
typedef long long ll; typedef unsigned long long ull;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define all(_X) (_X).begin(), (_X).end()

namespace {
	template<class T> inline void hash_combine(size_t& seed, T const& value) { seed ^= std::hash<T>()(value)+0x9e3779b9 + (seed << 6) + (seed >> 2); }
	template<class T, size_t Index = std::tuple_size<T>::value - 1> struct HashValueImpl { static void apply(size_t& seed, T const& tuple) { HashValueImpl<T, Index - 1>::apply(seed, tuple); hash_combine(seed, std::get<Index>(tuple)); } };
	template<class T> struct HashValueImpl<T, 0> { static void apply(size_t& seed, T const& tuple) { hash_combine(seed, std::get<0>(tuple)); } };
}
namespace std {
	template <typename ... TT> struct hash<tuple<TT...>> { size_t operator()(const tuple<TT...>& t) const { size_t seed = 0; HashValueImpl<tuple<TT...> >::apply(seed, t); return seed; } };
}

#define MEMOIZE(_Args, _Expr) do { auto&& _args = (std::make_tuple _Args); static std::map<typename std::remove_reference<decltype(_args)>::type, typename std::remove_reference<decltype(_Expr)>::type> _memo; auto&& _it = _memo.lower_bound(_args); if ( _it == _memo.end() || _it->first != _args ) { return _memo.emplace_hint(_it, std::move(_args), (_Expr))->second; } else { return _it->second; } } while(false)


int n, m, s[2];
vector<int> as[2];

int dfs(int,int);

int dfs_rec(int port, vector<int>::iterator const& lb)
{
	int ma = 0;
	for ( auto it = lb; it != as[port].end(); ++it ) {
		ma = max(ma, 1 + dfs(1 - port, *it + s[port]));
	}
	return ma;
}

int dfs(int port, int t)
{
	auto&& lb = lower_bound(all(as[port]), t);
	if ( lb != as[port].end() ) {
		t = *lb;
		echo(mkt(port, t));
		MEMOIZE((port, t), dfs_rec(port, lb));
	}
	return 0;
}

int main()
{
	cin >> n >> m >> s[0] >> s[1];
	as[0].resize(n);
	as[1].resize(m);
	rep(i, n)
	{
		cin >> as[0][i];
	}
	rep(i, m)
	{
		cin >> as[1][i];
	}

	cout << (dfs(0, 0) / 2) << endl;

	return 0;
}

Submission Info

Submission Time
Task C - 飛行機乗り
User vain0
Language C++14 (Clang++ 3.4)
Score 0
Code Size 2624 Byte
Status TLE
Exec Time 2042 ms
Memory 8732 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 8
TLE × 10
AC × 8
TLE × 25
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt TLE 2035 ms 2976 KB
subtask0_1.txt TLE 2042 ms 1696 KB
subtask0_10.txt TLE 2034 ms 1828 KB
subtask0_11.txt AC 106 ms 1316 KB
subtask0_12.txt TLE 2033 ms 3244 KB
subtask0_13.txt TLE 2034 ms 1700 KB
subtask0_14.txt AC 111 ms 1440 KB
subtask0_2.txt AC 105 ms 1312 KB
subtask0_3.txt TLE 2035 ms 2976 KB
subtask0_4.txt TLE 2036 ms 1828 KB
subtask0_5.txt AC 84 ms 1184 KB
subtask0_6.txt TLE 2036 ms 2968 KB
subtask0_7.txt TLE 2033 ms 1820 KB
subtask0_8.txt AC 84 ms 1184 KB
subtask0_9.txt TLE 2034 ms 2980 KB
subtask0_sample_01.txt AC 26 ms 928 KB
subtask0_sample_02.txt AC 24 ms 804 KB
subtask0_sample_03.txt AC 25 ms 736 KB
subtask1_0.txt TLE 2036 ms 8732 KB
subtask1_1.txt TLE 2035 ms 5532 KB
subtask1_10.txt TLE 2035 ms 4512 KB
subtask1_11.txt TLE 2035 ms 1820 KB
subtask1_12.txt TLE 2036 ms 8456 KB
subtask1_13.txt TLE 2036 ms 5796 KB
subtask1_14.txt TLE 2036 ms 1700 KB
subtask1_2.txt TLE 2034 ms 1824 KB
subtask1_3.txt TLE 2035 ms 7200 KB
subtask1_4.txt TLE 2035 ms 5540 KB
subtask1_5.txt TLE 2036 ms 1752 KB
subtask1_6.txt TLE 2035 ms 7840 KB
subtask1_7.txt TLE 2034 ms 5664 KB
subtask1_8.txt TLE 2036 ms 1708 KB
subtask1_9.txt TLE 2035 ms 8608 KB