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 |
|
|
|
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 |