結果

問題 No.2364 Knapsack Problem
ユーザー 👑 p-adicp-adic
提出日時 2023-07-01 14:03:52
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 3,000 ms
コード長 44,281 bytes
コンパイル時間 13,442 ms
コンパイル使用メモリ 302,416 KB
最終ジャッジ日時 2025-02-15 05:17:47
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 <bits/stdc++.h>
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<decltype( VAR )>
#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(
      "abortassert" ); }
void StartWatch( const string& process_name = "nothing" );
void StopWatch( const int& how_many_times = 1 );
#endif
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }
template <typename T> 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<TYPE_OF( ARGUMENT ),int>::value && ! is_same<TYPE_OF( ARGUMENT ),uint>::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 ); \
} \
} \
//
// EXPRESSIONANSWER調EXPRESSION >= TARGET
#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER ) \
static_assert( ! is_same<TYPE_OF( TARGET ),uint>::value && ! is_same<TYPE_OF( TARGET ),ull>::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<string> 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( "[y/n]" );
cin >> reply;
CERR( "" );
if( reply == "y" ){
CERR( "OEIS" );
CERR( "https://oeis.org/?language=japanese" );
CERR( "" );
CERR( "" );
CERR( "- 調" );
CERR( "- p使" );
CERR( "- pp" );
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( "Sa" );
CERR( "- si" );
CERR( " a[i]<=si" );
CERR( "- ia[i]Ss" );
CERR( " a[i]<=ss" );
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( "- " );
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( "maxmax調" );
CERR( "maxmax" );
CERR( "調" );
CERR( "調" );
CERR( "" );
CERR( "max{0,1}" );
CERR( "使" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "B_qmax(A_i,B_q)" );
CERR( "- A'={(A_i,i)|i}O(N log N)" );
CERR( "- (B_q,q)_qB'O(Q log Q)" );
CERR( "- NC=(0,...,0)O(N)" );
CERR( "B'(B_q,q)" );
CERR( "A'A_i<B_qi" );
CERR( "- A'(A_i,i)O(N)" );
CERR( "- A_i0O(N log N)" );
CERR( "- C_i1O(log N)" );
CERR( "- A+C×B_qO(log N)" );
CERR( "O((N + Q)log N + Q log Q)" );
}
} else if( num == num_temp++ ){
CERR( "fx" );
CERR( "- ixX(i)" );
CERR( "- ixi+1xdX(i)" );
CERR( "" );
CERR( "- O(sum_i X(i) dX(i))fxO(1)ix" );
CERR( "- O(N log_2 X(N))" );
CERR( " - fxO(N)x調x" );
CERR( " - fxO(N/x)x" );
CERR( "- O(N log_2 N)xfxO(log_2 N)" );
CERR( " x" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " " );
CERR( "- " );
CERR( " " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "gcdmax" );
CERR( "" );
} else if( num == num_temp++ ){
return LibrarySearch( num = num_subsequence_sum );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( " - O(N)" );
CERR( " - O(N)" );
CERR( "- " );
CERR( " \\Utility\\String\\RollingHash" );
CERR( "- Z" );
CERR( " https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N^2)Manacher" );
CERR( " https://snuke.hatenablog.com/entry/2014/12/02/235837" );
CERR( "" );
}
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- O(N^3)" );
CERR( "- O(N 2^N)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- O(N^2)" );
CERR( "- O(N log_2 N)BIT" );
CERR( " \\Mathematics\\Combinatorial\\Permutation" );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace\\BIT" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "i<j" );
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- 調" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- O(HW)" );
CERR( "- O(HW)" );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
CERR( "" );
CERR( "- BFSDijkstra" );
CERR( " \\Utility\\Search\\BreadthFirst" );
CERR( " \\Utility\\Search\\Dijkstra" );
CERR( "- " );
CERR( " - O(V^3)FloydWarshall" );
CERR( " \\Utility\\Search\\FloydWarshall" );
CERR( " - maxO(E(log_2 E + α(V)))UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "HeldKarp" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "\\Utility\\Search\\DepthFirst" );
CERR( "\\Utility\\VLTree" );
} else if( num == num_temp++ ){
CERR( "- 0UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "- " );
CERR( " \\Utility\\Search\\DepthFirst" );
CERR( "- " );
CERR( "" );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NWV" );
CERR( "- B=∞" );
CERR( "- B<∞O(2^N)" );
CERR( "- B<∞O(N 2^{N/2})" );
CERR( "- B<∞O(NV)[B-V,B+V]" );
CERR( " " );
CERR( " https://stackoverflow.com/a/18949218" );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
CERR( "- O(N 2^N)bit" );
} else if( num == num_temp++ ){
CERR( "NW" );
CERR( "- O(2^N)" );
CERR( "- O(2^N)" );
CERR( "- O(2^{N/2}N)" );
CERR( " " );
CERR( "- W10^5O((N+W)log_2 W)" );
CERR( " " );
CERR( " \\Mathematics\\Polynomial" );
}
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "- " );
CERR( "" );
CERR( "" );
CERR( "" );
CERR( "- " );
CERR( "- " );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
CERR( "- " );
CERR( " \\Mathematics\\SetTheory\\DirectProduct\\AffineSpace" );
CERR( "- UnionFind" );
CERR( " \\Utility\\VLTree\\UnionFindForest" );
CERR( "" );
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
""
);
if( num == num_temp++ ){
CERR( "NTK" );
CERR( "- O((N + T)log_2 K)" );
CERR( " \\Mathematics\\Function\\Iteration\\Doubling" );
CERR( "- O(TN)" );
CERR( " \\Mathematics\\Function\\Iteration\\LoopDetection" );
CERR( "- O(N)" );
CERR( "" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
}
} else if( num == num_temp++ ){
ASK_DETAILS(
"" ,
"" ,
"" ,
""
);
if( num == num_temp++ ){
CERR( "p" );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_graph );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
} else if( num == num_temp++ ){
CERR( "" );
return LibrarySearch( num = num_game );
}
}
CERR( "" );
CERR( "" );
CERR( "" );
return -1;
}
// Resetm_foundm_prev
// Shiftm_foundm_prev
#define DECLARATION_OF_FIRST_SEARCH( BREADTH ) \
template <int V_max> \
class BREADTH ## FirstSearch_Body \
{ \
\
protected: \
int m_V; \
int m_init; \
list<int> 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<int> e( const int& t ) = 0; \
\
}; \
\
template <int V_max,list<int> E(const int&)> \
class BREADTH ## FirstSearch : \
public BREADTH ## FirstSearch_Body<V_max> \
{ \
\
public: \
\
template<typename... Args> inline BREADTH ## FirstSearch( const Args&... args ); \
\
private: \
inline list<int> e( const int& t ); \
\
}; \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponent( const int& V , int ( &vertex )[V_max] , int& count ); \
#define DEFINITION_OF_FIRST_SEARCH( BREADTH , PUSH ) \
template <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::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 <int V_max> inline BREADTH ## FirstSearch_Body<V_max>::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 <int V_max,list<int> E(const int&)> template <typename... Args> inline BREADTH ## FirstSearch<V_max,E>::BREADTH ## FirstSearch( const
      Args&... args ) : BREADTH ## FirstSearch_Body<V_max>( args... ) {} \
\
template <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::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 <int V_max> inline void BREADTH ## FirstSearch_Body<V_max>::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 <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::size() const { return m_V; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::init() const { return m_init; } \
template <int V_max> inline bool& BREADTH ## FirstSearch_Body<V_max>::found( const int& i ) { assert( i < m_V ); return m_found[i]; } \
template <int V_max> inline const int& BREADTH ## FirstSearch_Body<V_max>::prev( const int& i ) const { assert( i < m_V ); return m_prev[i]; } \
\
template <int V_max> \
int BREADTH ## FirstSearch_Body<V_max>::Next() \
{ \
\
if( m_next.empty() ){ \
\
return -1; \
\
} \
\
const int i_curr = m_next.front(); \
m_next.pop_front(); \
list<int> 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 <int V_max,list<int> E(const int&)> inline list <int> BREADTH ## FirstSearch<V_max,E>::e( const int& t ) { return E( t ); } \
\
template <int V_max,list<int> E(const int&)> void BREADTH ## FirstConnectedComponentSearch( const int& V , int ( &vertex )[V_max] , int& count ) \
{ \
\
BREADTH ## FirstSearch<V_max,E> 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<int> 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<int> answer{}; \
int t_next = t; \
\
while( ( ( INCREMENT t_next ) OPERATION t ) < ULIM ){ \
\
UPDATE; \
\
} \
\
return answer \
DECLARATION_OF_FIRST_SEARCH( Breadth );
template <int digit>
class BitExhausiveSearch :
public BreadthFirstSearch_Body< ( 1 << digit ) >
{
private:
static map<int,int> g_v;
public:
inline BitExhausiveSearch( const int& V );
inline list<int> UnreachedAdjacentSupsetOf( const int& t ) noexcept;
inline list<int> UnreachedAdjacentSubsetOf( const int& t ) noexcept;
inline list<int> UnreachedProperSupsetOf( const int& t ) noexcept;
inline list<int> UnreachedProperSubsetOf( const int& t ) noexcept;
inline list<int> AdjacentSupsetOf( const int& t ) noexcept;
inline list<int> ProperSupsetOf( const int& t ) noexcept;
static inline list<int> AdjacentSubsetOf( const int& t ) noexcept;
static inline list<int> ProperSubsetOf( const int& t ) noexcept;
static inline const int& ValuationOf( const int& t ) noexcept;
private:
inline list<int> e( const int& t );
};
DEFINITION_OF_FIRST_SEARCH( Breadth , push_back );
template <int digit> map<int,int> BitExhausiveSearch<digit>::g_v{};
template <int digit> inline BitExhausiveSearch<digit>::BitExhausiveSearch( const int& V ) : BASE_FOR_BIT_EXHAUSIVE_SEARCH( V , 0 ) {}
template <int digit> inline list<int> BitExhausiveSearch<digit>::UnreachedAdjacentSupsetOf( const int& t ) noexcept { return e( t ); }
template <int digit> inline list<int> BitExhausiveSearch<digit>::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 <int digit> inline list<int> BitExhausiveSearch<digit>::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 <int digit> inline list<int> BitExhausiveSearch<digit>::AdjacentSupsetOf( const int& t ) noexcept { DEFINITION_OF_ADJACENT_SET( ~t , | ,
    BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , answer.push_back( t_next ) ); }
template <int digit> inline list<int> BitExhausiveSearch<digit>::ProperSupsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( ++ , |= ,
    BASE_FOR_BIT_EXHAUSIVE_SEARCH::m_V , answer.push_back( t_next ); ); }
template <int digit> inline list<int> BitExhausiveSearch<digit>::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 <int digit> inline list<int> BitExhausiveSearch<digit>::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 <int digit> inline list<int> BitExhausiveSearch<digit>::AdjacentSubsetOf( const int& t ) noexcept { DEFINITION_OF_ADJACENT_SET( t , ^ , t ,
    answer.push_back( t_next ) ); }
template <int digit> inline list<int> BitExhausiveSearch<digit>::ProperSubsetOf( const int& t ) noexcept { DEFINITION_OF_PROPER_SET( -- , ^= , t ,
    answer.push_back( t_next ); ); }
template <int digit> inline const int& BitExhausiveSearch<digit>::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 ); // 05
// CEXPR( int , bound_N , 1000000000 ); // 09
// CEXPR( ll , bound_N , 1000000000000000000 ); // 018
CIN_ASSERT( N , 1 , bound_N );
CEXPR( int , bound_M , 7 );
// DEXPR( int , bound_M , 100000 , 100 ); // 05
// // CEXPR( int , bound_M , 1000000000 ); // 09
// // CEXPR( ll , bound_M , 1000000000000000000 ); // 018
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<int,ll> wv[size_max];
int size = 1 << ( N + M );
FOR( s , 0 , size ){
wv[s].first = -1;
}
wv[0] = { 0 , 0 };
BitExhausiveSearch<bound_N + bound_M> bes{ size - 1 };
int s = bes.Next();
while( ( s = bes.Next() ) != -1 ){
list<int> a = bes.AdjacentSubsetOf( s );
FOR_ITR( a ){
pair<int,ll>& 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<int,ll>& 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0