#ifdef DEBUG #define _GLIBCXX_DEBUG #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ); signal( SIGABRT , &AlertAbort ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE ) #define CERR( ANSWER ) cerr << ANSWER << endl; #define COUT( ANSWER ) cout << ANSWER << endl #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " << ( MIN ) << ( ( MIN ) <= A ? "<=" : ">" ) << A << ( A <= ( MAX ) ? "<=" : ">" ) << ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) ) #define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; }; #define START_WATCH( PROCESS_NAME ) StartWatch( PROCESS_NAME ) #define STOP_WATCH( HOW_MANY_TIMES ) StopWatch( HOW_MANY_TIMES ) #else #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE ) #define CERR( ANSWER ) #define COUT( ANSWER ) cout << ANSWER << "\n" #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define LIBRARY_SEARCH #define START_WATCH( PROCESS_NAME ) #define STOP_WATCH( HOW_MANY_TIMES ) #endif #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; #define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) ) #define TYPE_OF( VAR ) decay_t #define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX ) #define GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define AUTO_ITR( ARRAY ) auto itr_ ## ARRAY = ARRAY .begin() , end_ ## ARRAY = ARRAY .end() #define FOR_ITR( ARRAY ) for( AUTO_ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS_ ) #define RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT #ifdef DEBUG inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); } void StartWatch( const string& process_name = "nothing" ); void StopWatch( const int& how_many_times = 1 ); #endif template inline T Absolute( const T& a ){ return a > 0 ? a : -a; } template inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; } #define POWER( ANSWER , ARGUMENT , EXPONENT ) \ static_assert( ! is_same::value && ! is_same::value ); \ TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \ { \ TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ ll ANSWER{ 1 }; \ { \ ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( ( MODULO ) + ( ( ARGUMENT ) % ( MODULO ) ) ) % ( MODULO ); \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % ( MODULO ); \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \ static ll ANSWER[CONSTEXPR_LENGTH]; \ static ll ANSWER_INV[CONSTEXPR_LENGTH]; \ static ll INVERSE[CONSTEXPR_LENGTH]; \ { \ ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \ ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \ FOREQ( i , 1 , MAX_INDEX ){ \ ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= ( MODULO ); \ } \ ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \ FOREQ( i , 2 , MAX_INDEX ){ \ ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = ( MODULO ) - ( ( ( ( MODULO ) / i ) * INVERSE[ ( MODULO ) % i ] ) % ( MODULO ) ) ) %= ( MODULO ); \ } \ } \ // 二分探索テンプレート // EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= TARGETの整数解を格納。 #define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \ static_assert( ! is_same::value && ! is_same::value ); \ ll ANSWER = MINIMUM; \ if( MINIMUM <= MAXIMUM ){ \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ CERR( "二分探索中: " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << "-" << TARGET << "=" << VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH INEQUALITY_FOR_CHECK 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_U = UPDATE_U; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_L = UPDATE_L; \ } \ ANSWER = UPDATE_ANSWER; \ } \ CERR( "二分探索終了: " << VARIABLE_FOR_BINARY_SEARCH_L << "<=" << ANSWER << "<=" << VARIABLE_FOR_BINARY_SEARCH_U << ":" << EXPRESSION << ( EXPRESSION > TARGET ? ">" : EXPRESSION < TARGET ? "<" : "=" ) << TARGET ); \ CERR( ( EXPRESSION DESIRED_INEQUALITY TARGET ? "二分探索成功" : "二分探索失敗" ) ); \ assert( EXPRESSION DESIRED_INEQUALITY TARGET ); \ } else { \ CERR( "二分探索失敗: " << MINIMUM << ">" << MAXIMUM ); \ assert( MINIMUM <= MAXIMUM ); \ } \ // 単調増加の時にEXPRESSION >= TARGETの最小解を格納。 #define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , >= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調増加の時にEXPRESSION <= TARGETの最大解を格納。 #define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , > , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調減少の時にEXPRESSION >= TARGETの最大解を格納。 #define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , TARGET , < , ANSWER - 1 , ANSWER , ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 単調減少の時にEXPRESSION <= TARGETの最小解を格納。 #define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , TARGET , <= , ANSWER , ANSWER + 1 , ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2 ) \ // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& #define ASK_DETAILS( ... ) \ CERR( "問題の区分は以下の中で何番に該当しますか?" ); \ problems = { __VA_ARGS__ }; \ problems_size = problems.size(); \ FOR( i , 0 , problems_size ){ \ CERR( i << ": " << problems[i] ); \ } \ cin >> num; \ CERR( "" ); \ num_temp = 0; \ if( num < 0 || num >= problems_size ){ \ CERR( "返答は" << problems_size - 1 << "以下の非負整数にしてください。" ); \ CERR( "終了します。" ); \ CERR( "" ); \ return -1; \ } \ int LibrarySearch( int num = -1 ) { vector problems{}; int problems_size = 13; int num_temp = 0; string reply{}; if( num == -1 ){ CERR( "ライブラリーを探索しますか?[y/n]" ); cin >> reply; if( reply == "n" ){ CERR( "ライブラリーを探索せずに続行します。" ); CERR( "" ); return 0; } else if( reply != "y" ){ CERR( "y/nのいずれかで答えてください。" ); CERR( "終了します。" ); CERR( "" ); return -1; } CERR( "" ); CERR( "ライブラリーを探索します。" ); ASK_DETAILS( "数や関数に関する問題。" , "配列に関する問題。" , "文字列に関する問題。" , "順列に関する問題。" , "矩形領域に関する問題。" , "グラフに関する問題。" , "部分和問題。" , "確率/期待値に関する問題。" , "ゲームに関する問題。" , "論理に関する問題。" , "半順序集合に関する問題。" , "関数適用に関する問題。" , "構築問題。" ); } else { CERR( "" ); } CEXPR( int , num_graph , 5 ); CEXPR( int , num_subsequence_sum , 6 ); CEXPR( int , num_game , 8 ); if( num == num_temp++ ){ CERR( "入力は1つの数か、1つの数と法を表す数ですか?[y/n]" ); cin >> reply; CERR( "" ); if( reply == "y" ){ CERR( "まずは小さい入力の場合を愚直に計算し、OEISで検索しましょう。" ); CERR( "https://oeis.org/?language=japanese" ); CERR( "" ); CERR( "次に出力の定義と等価な式を考察しましょう。" ); CERR( "- 単調ならば、冪乗や階乗" ); CERR( "- 定義にp進法が使われていれば、各種探索アルゴリズム" ); CERR( "- 入力が素数に近い場合に規則性があれば、p進付値、p進法、" ); CERR( " オイラー関数、約数の個数など" ); CERR( "を検討しましょう。" ); } else if( reply == "n" ){ ASK_DETAILS( "求解問題。" , "最大化問題。" , "数え上げ問題。" , "ソート問題。" ); if( num == num_temp++ ){ CERR( "まず" ); CERR( "- 単調関数は二分探索" ); CERR( "- 可微分関数はニュートン法" ); CERR( "- 一次関数は掃き出し法" ); CERR( "を検討しましょう。" ); CERR( "" ); CERR( "それらが間に合わない時は" ); CERR( "- 探索範囲を絞れそうな場合は全探策" ); CERR( "- 多変数の合成関数で表せる場合は半分全列挙" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 凸関数は三分探索" ); CERR( "- 可微分関数は微分のニュートン法" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 変数の対称性があれば大小関係を制限した全探策" ); CERR( "- 何らかの約数となるなど動く範囲が狭い変数があればそれらを決め打った全探策" ); CERR( "- 多変数の合成関数で表せる場合は半分全列挙" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "集合Sを何らかの順序でソートした配列aに関する問題で、" ); CERR( "- 与えられた要素sが下から何番目かを答える場合は、非負整数iごとに" ); CERR( " 不等式a[i]<=sを判定する方法を考察し、iに関する二分探索" ); CERR( "- 与えられた非負整数iに対するa[i]を答える場合は、Sの要素sごとに" ); CERR( " 不等式a[i]<=sを判定する方法を考察し、sに関する二分探索" ); CERR( "を検討しましょう。" ); } } else { CERR( "y/nのいずれかで答えてください。" ); CERR( "終了します。" ); CERR( "" ); return -1; } CERR( "" ); CERR( "マルチテストケースですか?[y/n]" ); cin >> reply; CERR( "" ); if( reply == "y" ){ CERR( "テストケース全体でのNの総和に直接上限が与えられている問題では、" ); CERR( "ライブラリーの使用時は、配列の初期化が各テストケースに必要となる場合に" ); CERR( "TLEとなる可能性が高いです。適宜動的配列に置き換えましょう。" ); CERR( "" ); CERR( "配列を手元の環境でデバッグしやすくするためにstaticをつけている場合は" ); CERR( "テストケースを跨いで値が残ってしまわないように注意しましょう。" ); CERR( "" ); CERR( "前計算の候補としては" ); CERR( "- 素数列挙" ); CERR( "- 1つまたは複数の整数の約数列挙" ); CERR( "- オイラー関数の値の列挙" ); CERR( "- サブゴールとなる関係式を満たす解の列挙" ); CERR( "を検討しましょう。" ); } else if( reply == "n" ){ CERR( "入力が大きい場合と小さい場合で解法を変える考察を忘れないようにしましょう。" ); } else { CERR( "y/nのいずれかで答えてください。" ); CERR( "終了します。" ); CERR( "" ); return -1; } CERR( "" ); } else if( num == num_temp++ ){ ASK_DETAILS( "区間処理問題。" , "最大化問題。" , "最長部分列問題。" , "数え上げ問題。" , "部分和問題。" ); if( num == num_temp++ ){ ASK_DETAILS( "可換群構造+を使う問題。" , "可換羃等モノイド構造∨を使う問題。" , "モノイド構造*を使う問題。" , "非結合的マグマ構造*を使う問題。" , "集合へのマグマ作用(*,\\cdot)を使う問題。" , "モノイドへのマグマ作用(+,\\cdot)を使う問題。" , "定数とのmaxを取った値の区間和取得を使う問題。" ); if( num == num_temp++ ){ CERR( "- 区間加算/区間取得が必要ならば可換群BIT" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template" ); CERR( "- 一点代入/一点加算/区間取得が必要ならば可換群平方分割" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template" ); CERR( "- 区間以外の領域で加算/全更新後の一点取得が必要ならば階差数列" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\Tree\\DifferenceSeqeuence" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 一点代入/区間加算/一点取得/区間取得が必要ならば可換羃等モノイドBIT" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\IntervalMax\\Template" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 一点代入/区間取得が必要ならばモノイドBIT" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT\\Template\\Monoid" ); CERR( "- 一点加算/区間加算/一点取得/区間取得が必要ならばモノイド平方分割" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Monoid" ); CERR( "- 一点代入/一点取得/区間取得が必要ならばモノイドセグメント木" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SegmentTree" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 写像のコード化" ); CERR( " \\Mathematics\\Function\\Encoder" ); CERR( "によりモノイドに帰着させることを検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 一点作用/区間作用/一点取得が必要ならば双対平方分割" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\Dual" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "- 区間代入/区間作用/区間加算/一点取得/区間取得が必要な場合は遅延評価平方分割" ); CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\SqrtDecomposition\\Template\\LazyEvaluation" ); CERR( "を検討しましょう。" ); } else if( num == num_temp++ ){ CERR( "maxで全体更新でなく区間更新をする場合の汎用的な解法は分かりません。" ); CERR( "例えば区間が包含について単調でmaxを取る値も単調であれば全体更新と" ); CERR( "同様の処理ができます。状況に応じた考察をしましょう。" ); CERR( "" ); CERR( "maxで全体更新をする場合、maxを取る値は単調である場合に帰着できます。" ); CERR( "maxで全体更新をしない場合、つまりただmaxの区間和を処理するだけの場合、" ); CERR( "クエリの順番を入れ替えることができるので、単調な全体更新に帰着できます。" ); CERR( "従って以下では単調な全体更新の問題を考えます。" ); CERR( "" ); CERR( "maxを取る定数を変数化し、元の値との大小を表す{0,1}値の係数を考えます。" ); CERR( "すると区間作用前後の値は統一的にその係数と変数を使って表せます。" ); CERR( "配列の各成分の係数の値が変化するイベントとクエリをソートして管理し、" ); CERR( "クエリがイベントを跨ぐたびに係数を更新することを検討しましょう。" ); CERR( "" ); CERR( "例えばクエリB_qに対するmax(A_i,B_q)の区間和は、" ); CERR( "- 優先度つきキューA'={(A_i,i)|i}(構築O(N log N))" ); CERR( "- (B_q,q)_qをソートしたB'(構築O(Q log Q))" ); CERR( "- 長さNの数列C=(0,...,0)(構築O(N))" ); CERR( "を用意し、B'を前から探索して順に各クエリ(B_q,q)を処理します。" ); CERR( "具体的にはA'を前から探索して順にA_i \ class BREADTH ## FirstSearch_Body \ { \ \ protected: \ int m_V; \ int m_init; \ list m_next; \ bool m_found[V_max]; \ int m_prev[V_max]; \ \ public: \ inline BREADTH ## FirstSearch_Body( const int& V ); \ inline BREADTH ## FirstSearch_Body( const int& V , const int& init ); \ \ inline void Reset( const int& init ); \ inline void Shift( const int& init ); \ \ inline const int& size() const; \ inline const int& init() const; \ inline bool& found( const int& i ); \ inline const int& prev( const int& i ) const; \ \ int Next(); \ \ private: \ virtual list e( const int& t ) = 0; \ \ }; \ \ template E(const int&)> \ class BREADTH ## FirstSearch : \ public BREADTH ## FirstSearch_Body \ { \ \ public: \ \ template inline BREADTH ## FirstSearch( const Args&... args ); \ \ private: \ inline list e( const int& t ); \ \ }; \ \ template E(const int&)> void BREADTH ## FirstConnectedComponent( const int& V , int ( &vertex )[V_max] , int& count ); \ #define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \ template inline BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body( const int& V ) : m_V( V ) , m_init() , m_next() , m_found() , m_prev() { assert( m_V <= V_max ); for( int i = 0 ; i < m_V ; i++ ){ m_prev[i] = -1; } } \ template inline BREADTH ## FirstSearch_Body::BREADTH ## FirstSearch_Body( const int& V , const int& init ) : BREADTH ## FirstSearch_Body( V ) { m_init = init; m_next.push_back( m_init ); m_found[m_init] = true; } \ template E(const int&)> template inline BREADTH ## FirstSearch::BREADTH ## FirstSearch( const Args&... args ) : BREADTH ## FirstSearch_Body( args... ) {} \ \ template inline void BREADTH ## FirstSearch_Body::Reset( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); m_next.push_back( m_init ); for( int i = 0 ; i < m_V ; i++ ){ m_found[i] = i == m_init; m_prev[i] = -1; } } \ template inline void BREADTH ## FirstSearch_Body::Shift( const int& init ) { m_init = init; assert( m_init < m_V ); m_next.clear(); if( ! m_found[m_init] ){ m_next.push_back( m_init ); m_found[m_init] = true; } } \ \ template inline const int& BREADTH ## FirstSearch_Body::size() const { return m_V; } \ template inline const int& BREADTH ## FirstSearch_Body::init() const { return m_init; } \ template inline bool& BREADTH ## FirstSearch_Body::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \ template inline const int& BREADTH ## FirstSearch_Body::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \ \ template \ int BREADTH ## FirstSearch_Body::Next() \ { \ \ if( m_next.empty() ){ \ \ return -1; \ \ } \ \ const int i_curr = m_next.front(); \ m_next.pop_front(); \ list edge = e( i_curr ); \ \ while( ! edge.empty() ){ \ \ const int& i = edge.front(); \ bool& found_i = found( i ); \ \ if( ! found_i ){ \ \ m_next.PUSH( i ); \ m_prev[i] = i_curr; \ found_i = true; \ \ } \ \ edge.pop_front(); \ \ } \ \ return i_curr; \ \ } \ \ template E(const int&)> inline list BREADTH ## FirstSearch::e( const int& t ) { return E( t ); } \ \ template E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &vertex )[V_max] , int& count ) \ { \ \ BREADTH ## FirstSearch bfs{ V }; \ count = 0; \ \ for( int i = 0 ; i < V ; i++ ){ \ \ vertex[i] = -1; \ \ } \ \ for( int i = 0 ; i < V ; i++ ){ \ \ if( vertex[i] == -1 ){ \ \ bfs.Shift( i ); \ int j = bfs.Next(); \ \ while( j != -1 ? vertex[j] == 0 : false ){ \ \ vertex[j] = count; \ j = bfs.Next(); \ \ } \ \ count++; \ \ } \ \ } \ \ return; \ \ } \ #define BASE_FOR_BIT_EXHAUSIVE_SEARCH BreadthFirstSearch_Body< ( 1 << digit ) > #define DEFINITION_OF_ADJACENT_SET( T_COPY , OPERATION , ULIM , UPDATE ) \ list answer{}; \ int t_copy = T_COPY; \ int t_next; \ int d; \ \ while( t_copy != 0 && ( t_next = ( t OPERATION ( d = ( t_copy & -t_copy ) ) ) ) < ULIM ){ \ \ t_copy -= d; \ UPDATE; \ \ } \ \ return answer \ #define DEFINITION_OF_PROPER_SET( INCREMENT , OPERATION , ULIM , UPDATE ) \ list answer{}; \ int t_next = t; \ \ while( ( ( INCREMENT t_next ) OPERATION t ) < ULIM ){ \ \ UPDATE; \ \ } \ \ return answer \ DECLARATION_OF_FIRST_SEARCH( Breadth ); template class BitExhausiveSearch : public BreadthFirstSearch_Body< ( 1 << digit ) > { private: static map g_v; public: inline BitExhausiveSearch( const int& V ); inline list UnreachedAdjacentSupsetOf( const int& t ) noexcept; inline list UnreachedAdjacentSubsetOf( const int& t ) noexcept; inline list UnreachedProperSupsetOf( const int& t ) noexcept; inline list UnreachedProperSubsetOf( const int& t ) noexcept; inline list AdjacentSupsetOf( const int& t ) noexcept; inline list ProperSupsetOf( const int& t ) noexcept; static inline list AdjacentSubsetOf( const int& t ) noexcept; static inline list ProperSubsetOf( const int& t ) noexcept; static inline const int& ValuationOf( const int& t ) noexcept; private: inline list e( const int& t ); }; DEFINITION_OF_FIRST_SEARCH( Breadth , push_back ); template map BitExhausiveSearch::g_v{}; template inline BitExhausiveSearch::BitExhausiveSearch( const int& V ) : BASE_FOR_BIT_EXHAUSIVE_SEARCH( V , 0 ) {} template inline list BitExhausiveSearch::UnreachedAdjacentSupsetOf( const int& t ) noexcept { return e( t ); } template inline list BitExhausiveSearch::e( const int& t ) { DEFINITION_OF_ADJACENT_SET( ~t , | , BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , if( ! BASE_FOR_BIT_EXHAUSIVE_SEARCH::found( t_next ) ){ answer.push_back( t_next ); } ); } template inline list BitExhausiveSearch::UnreachedProperSupsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( ++ , |= , BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , if( ! BASE_FOR_BIT_EXHAUSIVE_SEARCH::found( t_next ) ){ answer.push_back( t_next ); } ); } template inline list BitExhausiveSearch::AdjacentSupsetOf( const int& t ) noexcept { DEFINITION_OF_ADJACENT_SET( ~t , | , BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , answer.push_back( t_next ) ); } template inline list BitExhausiveSearch::ProperSupsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( ++ , |= , BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , answer.push_back( t_next ); ); } template inline list BitExhausiveSearch::UnreachedAdjacentSubsetOf( const int& t ) noexcept { DEFINITION_OF_ADJACENT_SET( t , ^ , t , if( ! BASE_FOR_BIT_EXHAUSIVE_SEARCH::found( t_next ) ){ answer.push_back( t_next ); } ); } template inline list BitExhausiveSearch::UnreachedProperSubsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( -- , ^= , t , if( ! BASE_FOR_BIT_EXHAUSIVE_SEARCH::found( t_next ) ){ answer.push_back( t_next ); } ); } template inline list BitExhausiveSearch::AdjacentSubsetOf( const int& t ) noexcept { DEFINITION_OF_ADJACENT_SET( t , ^ , t , answer.push_back( t_next ) ); } template inline list BitExhausiveSearch::ProperSubsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( -- , ^= , t , answer.push_back( t_next ); ); } template inline const int& BitExhausiveSearch::ValuationOf( const int& t ) noexcept { if( g_v.empty() ){ for( int d = 0 ; d < digit ; d++ ){ g_v[ 1 << d ] = d; } } return g_v[t]; } int main() { UNTIE; LIBRARY_SEARCH; // DEXPR( int , bound_T , 100000 , 100 ); // CIN_ASSERT( T , 1 , bound_T ); // REPEAT( T ){ // } CEXPR( int , bound_N , 7 ); // DEXPR( int , bound_N , 100000 , 100 ); // 0が5個 // CEXPR( int , bound_N , 1000000000 ); // 0が9個 // CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個 CIN_ASSERT( N , 1 , bound_N ); CEXPR( int , bound_M , 7 ); // DEXPR( int , bound_M , 100000 , 100 ); // 0が5個 // // CEXPR( int , bound_M , 1000000000 ); // 0が9個 // // CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個 CIN_ASSERT( M , 1 , bound_M ); CEXPR( int , bound_W , 500 ); CIN_ASSERT( W , 1 , bound_W ); CEXPR( int , bound_BD , 100000000 ); int A[bound_N + bound_M]; FOR( i , 0 , N ){ CIN_ASSERT( Ai , 1 , W ); A[i] = Ai; } int B[bound_N + bound_M]; FOR( i , 0 , N ){ CIN_ASSERT( Bi , 1 , bound_BD ); B[i] = Bi; } FOR( i , 0 , M ){ CIN_ASSERT( Ci , 1 , W ); A[i + N] = -Ci; } FOR( i , 0 , M ){ CIN_ASSERT( Di , 1 , bound_BD ); B[i + N] = -Di; } CEXPR( int , size_max , 1 << ( bound_N + bound_M ) ); pair wv[size_max]; int size = 1 << ( N + M ); FOR( s , 0 , size ){ wv[s].first = -1; } wv[0] = { 0 , 0 }; BitExhausiveSearch bes{ size - 1 }; int s = bes.Next(); while( ( s = bes.Next() ) != -1 ){ list a = bes.AdjacentSubsetOf( s ); FOR_ITR( a ){ pair& wv_t = wv[*itr]; if( 0 <= wv_t.first && wv_t.first <= W ){ const int& v = bes.ValuationOf( *itr ^ s ); wv[s] = { wv_t.first + A[v] , wv_t.second + B[v] }; break; } } } ll answer = 0; FOR( s , 0 , size ){ pair& wv_s = wv[s]; if( wv_s.first <= W ){ answer = max( answer , wv_s.second ); } } // CEXPR( ll , P , 998244353 ); // CEXPR( ll , P , 1000000007 ); // DEXPR( int , bound_Q , 100000 , 100 ); // CIN_ASSERT( Q , 1 , bound_Q ); // REPEAT( Q ){ // COUT( N ); // } RETURN( answer ); // QUIT; }