結果
問題 | No.2617 容量3のナップザック |
ユーザー |
👑 |
提出日時 | 2023-12-19 22:24:25 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 15,890 bytes |
コンパイル時間 | 14,475 ms |
コンパイル使用メモリ | 298,824 KB |
最終ジャッジ日時 | 2025-02-18 12:20:56 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
// 入力フォーマットチェック#ifdef INCLUDE_MAINinline void Solve(){GETLINE_COUNT( NKseedab_str , 6 , " " );CEXPR( int , bound_N , 1000000 ); // 0が6個STOI( NKseedab_str , N , bound_N );STOI( NKseedab_str , K , N );CEXPR( ll , bound_m , 1000000000 ); // 0が9個STOI( NKseedab_str , seed , bound_m );STOI( NKseedab_str , a , bound_m );STOI( NKseedab_str , b , bound_m );STOI( NKseedab_str , m , bound_m );ll f[2*N] = {seed};FOR( i , 1 , 2*N ){f[i] = ( a * f[i-1] + b ) % m;}vector<ll> v[4];int length[4] = { 0 , 3 * K + 3 , K + 1 , K + 1 };FOREQ( w , 1 , 3 ){v[w].reserve( length[w] );v[w].push_back( -1000000000000000000 );}FOR( i , 0 , N ){ll wi = f[i] % 3 + 1;v[wi].push_back( - wi * f[i + N] );}FOREQ( w , 1 , 3 ){sort( v[w].begin() , v[w].end() );v[w][0] = 0;int size = v[w].size();FOR( i , 1 , size ){v[w][i] = - v[w][i] + v[w][i-1];}while( size < length[w] ){v[w].push_back( v[w].back() );size++;}}ll answer = v[3][K];FOR( k3 , 0 , K ){int k2 = 0;if( v[2][1] >= v[1][K*3-k3*3] - v[1][K*3-k3*3-2] ){auto f = [&]( const int& k ){ return ( v[2][k] - v[2][k-1] ) - ( v[1][K*3-k3*3-k*2+2] - v[1][K*3-k3*3-k*2] ); };BS3( k , 1 , K - k3 , f( k ) , 0 );k2 = k;}int k1 = K*3-k3*3-k2*2;answer = max( answer , v[3][k3] + v[2][k2] + v[1][k1] );}RETURN( answer );}REPEAT_MAIN(1);#else // INCLUDE_MAIN#ifdef INCLUDE_SUB// VVV テンプレート引数用の関数は以下に挿入する。// AAA テンプレート引数用の関数は以上に挿入する。#define INCLUDE_MAIN#include __FILE__#else // INCLUDE_SUB#ifdef INCLUDE_LIBRARY// 圧縮用#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&// https://github.com/p-adic/cpp// VVV ライブラリは以下に挿入する。// 二分探索用// EXPRESSIONがANSWERの広義単調関数の時、EXPRESSION >= CONST_TARGETの整数解を格納。#define BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , DESIRED_INEQUALITY , CONST_TARGET , INEQUALITY_FOR_CHECK , UPDATE_U , UPDATE_L , UPDATE_ANSWER) \static_assert( ! is_same<TYPE_OF( CONST_TARGET ),uint>::value && ! is_same<TYPE_OF( CONST_TARGET ),ull>::value ); \ll ANSWER = MINIMUM; \{ \ll L_BS = MINIMUM; \ll U_BS = MAXIMUM; \ANSWER = UPDATE_ANSWER; \ll EXPRESSION_BS; \const ll CONST_TARGET_BS = ( CONST_TARGET ); \ll DIFFERENCE_BS; \while( L_BS < U_BS ){ \DIFFERENCE_BS = ( EXPRESSION_BS = ( EXPRESSION ) ) - CONST_TARGET_BS; \CERR( "二分探索中:" , "L_BS =" , L_BS , "<=" , ANSWER , "<=" , U_BS , "= U_BS :" , #EXPRESSION , "-" , #CONST_TARGET , "=" , EXPRESSION_BS , "-", CONST_TARGET_BS , "=" , DIFFERENCE_BS ); \if( DIFFERENCE_BS INEQUALITY_FOR_CHECK 0 ){ \U_BS = UPDATE_U; \} else { \L_BS = UPDATE_L; \} \ANSWER = UPDATE_ANSWER; \} \if( L_BS > U_BS ){ \CERR( "二分探索失敗:" , "L_BS =" , L_BS , ">" , U_BS , "= U_BS :" , #ANSWER , ":=" , #MAXIMUM , "+ 1 =" , MAXIMUM + 1 ); \CERR( "二分探索マクロにミスがある可能性があります。変更前の版に戻してください。" ); \ANSWER = MAXIMUM + 1; \} else { \CERR( "二分探索終了:" , "L_BS =" , L_BS , "<=" , ANSWER , "<=" , U_BS , "= U_BS" ); \CERR( "二分探索が成功したかを確認するために" , #EXPRESSION , "を計算します。" ); \CERR( "成功判定が不要な場合はこの計算を削除しても構いません。" ); \EXPRESSION_BS = ( EXPRESSION ); \CERR( "二分探索結果:" , #EXPRESSION , "=" , EXPRESSION_BS , ( EXPRESSION_BS > CONST_TARGET_BS ? ">" : EXPRESSION_BS < CONST_TARGET_BS ? "<" : "=" ) , CONST_TARGET_BS ); \if( EXPRESSION_BS DESIRED_INEQUALITY CONST_TARGET_BS ){ \CERR( "二分探索成功:" , #ANSWER , ":=" , ANSWER ); \} else { \CERR( "二分探索失敗:" , #ANSWER , ":=" , #MAXIMUM , "+ 1 =" , MAXIMUM + 1 ); \CERR( "単調でないか、単調増加性と単調減少性を逆にしてしまったか、探索範囲内に解が存在しません。" ); \ANSWER = MAXIMUM + 1; \} \} \} \// 単調増加の時にEXPRESSION >= CONST_TARGETの最小解を格納。#define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , CONST_TARGET ) \BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , CONST_TARGET , >= , ANSWER , ANSWER + 1 , ( L_BS + U_BS ) / 2 ) \// 単調増加の時にEXPRESSION <= CONST_TARGETの最大解を格納。#define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , CONST_TARGET ) \BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , CONST_TARGET , > , ANSWER - 1 , ANSWER , ( L_BS + 1 + U_BS ) / 2 ) \// 単調減少の時にEXPRESSION >= CONST_TARGETの最大解を格納。#define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , CONST_TARGET ) \BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , >= , CONST_TARGET , < , ANSWER - 1 , ANSWER , ( L_BS + 1 + U_BS ) / 2 ) \// 単調減少の時にEXPRESSION <= CONST_TARGETの最小解を格納。#define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , CONST_TARGET ) \BS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , <= , CONST_TARGET , <= , ANSWER , ANSWER + 1 , ( L_BS + U_BS ) / 2 ) \// AAA ライブラリは以上に挿入する。#define INCLUDE_SUB#include __FILE__#else // INCLUDE_LIBRARY// #define REACTIVE#define USE_GETLINE#ifdef DEBUG#define _GLIBCXX_DEBUG#define SIGNAL signal( SIGABRT , &AlertAbort );#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )#define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック: " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX )); assert( ( MIN ) <= A && A <= ( MAX ) )#define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl#define COUT( ... ) VariadicCout( cout << "出力: " , __VA_ARGS__ ) << endl#define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl#define COUT_A( A , N ) cout << "出力: "; OUTPUT_ARRAY( cout , A , N ) << endl#define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl#define COUT_ITR( A ) cout << "出力: "; OUTPUT_ITR( cout , A ) << endl#else#pragma GCC optimize ( "O3" )#pragma GCC optimize ( "unroll-loops" )#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )#define SIGNAL#define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )#define CERR( ... )#define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL#define CERR_A( A , N )#define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << ENDL#define CERR_ITR( A )#define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << ENDL#endif#ifdef REACTIVE#define ENDL endl#else#define ENDL "\n"#endif#ifdef USE_GETLINE#define SET_LL( A ) { GETLINE( A ## _str ); A = stoll( A ## _str ); }#define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )#define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )#else#define SET_LL( A ) cin >> A#define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )#define SET_A( A , N ) FOR( VARIABLE_FOR_CIN_A , 0 , N ){ cin >> A[VARIABLE_FOR_CIN_A]; }#define CIN_A( LL , A , N ) vector<LL> A( N ); SET_A( A , N );#endif#include <bits/stdc++.h>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;using ld = long double;using lld = __float128;template <typename INT> using T2 = pair<INT,INT>;template <typename INT> using T3 = tuple<INT,INT,INT>;template <typename INT> using T4 = tuple<INT,INT,INT,INT>;#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND ,min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); }REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR("" ); } CHECK_REDUNDANT_INPUT; }#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now()#define CURRENT_TIME static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 )#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME < TL_MS - 100.0 )#define TYPE_OF( VAR ) decay_t<decltype( VAR )>#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE#define SET_ASSERT( A , MIN , MAX ) SET_LL( A ); ASSERT( A , MIN , MAX )#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_ASSERT( A , MIN , MAX )#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 + 1 > 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 SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS )#define OUTPUT_ARRAY( OS , A , N ) FOR( VARIABLE_FOR_OUTPUT_ARRAY , 0 , N ){ OS << A[VARIABLE_FOR_OUTPUT_ARRAY] << (VARIABLE_FOR_OUTPUT_ARRAY==N-1?"":" "); } OS#define OUTPUT_ITR( OS , A ) { auto ITERATOR_FOR_OUTPUT_ITR = A.begin() , END_FOR_OUTPUT_ITR = A.end(); bool VARIABLE_FOR_OUTPUT_ITR =ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR; while( VARIABLE_FOR_OUTPUT_ITR ){ OS << *ITERATOR_FOR_COUT_ITR; ( VARIABLE_FOR_OUTPUT_ITR =++ITERATOR_FOR_COUT_ITR != END_FOR_COUT_ITR ) ? OS : OS << " "; } } OS#define RETURN( ... ) COUT( __VA_ARGS__ ); return// 入出力用template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg ,ARGS&... args ) { return VariadicCin( is >> arg , args... ); }template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , constchar& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }template <class Traits , typename Arg> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const vector<Arg>& arg ) {auto begin = arg.begin() , end = arg.end(); auto itr = begin; while( itr != end ){ ( itr == begin ? os : os << " " ) << *itr; itr++; } return os;}template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os<< arg; }template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }// デバッグ用#ifdef DEBUGinline void AlertAbort( int n ) { CERR("abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }void AutoCheck( bool& auto_checked );#endif// 入力フォーマットチェック用// 1行中の変数の個数をSEPARATOR区切りで確認#define GETLINE_COUNT( S , VARIABLE_NUMBER , SEPARATOR ) GETLINE( S ); int VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S = 0; intVARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S = S.size(); { int size = S.size(); int count = 0; for( int i = 0 ; i < size ; i++ ){ if( S.substr( i , 1) == SEPARATOR ){ count++; } } assert( count + 1 == VARIABLE_NUMBER ); }// 余計な入力の有無を確認#ifdef DEBUG#define CHECK_REDUNDANT_INPUT#else#ifdef USE_GETLINE#define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; getline( cin , VARIABLE_FOR_CHECK_REDUNDANT_INPUT ); assert(VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )#else#define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert(VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )#endif#endif// |N| <= BOUNDを満たすNをSから構築#define STOI( S , N , BOUND ) TYPE_OF( BOUND ) N = 0; { bool VARIABLE_FOR_POSITIVITY_FOR_GETLINE = true; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); if( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) == "-" ){VARIABLE_FOR_POSITIVITY_FOR_GETLINE = false; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); } assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) != " " ); stringVARIABLE_FOR_LETTER_FOR_GETLINE{}; int VARIABLE_FOR_DIGIT_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) != " " :false ){ VARIABLE_FOR_DIGIT_FOR_GETLINE = stoi( VARIABLE_FOR_LETTER_FOR_GETLINE ); assert( N < BOUND / 10 ? true : N == BOUND / 10 &&VARIABLE_FOR_DIGIT_FOR_GETLINE <= BOUND % 10 ); N = N * 10 + VARIABLE_FOR_DIGIT_FOR_GETLINE; VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } if( !VARIABLE_FOR_POSITIVITY_FOR_GETLINE ){ N *= -1; } if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }// SをSEPARATORで区切りTを構築#define SEPARATE( S , T , SEPARATOR ) string T{}; { assert( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S < VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ); intVARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev = VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S; assert( S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_## S , 1 ) != SEPARATOR ); string VARIABLE_FOR_LETTER_FOR_GETLINE{}; while( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ? ( VARIABLE_FOR_LETTER_FOR_GETLINE = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S , 1 ) ) !=SEPARATOR : false ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } T = S.substr( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ,VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S - VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S_prev ); if( VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S <VARIABLE_FOR_SIZE_FOR_GETLINE_FOR_ ## S ){ VARIABLE_FOR_INDEX_FOR_GETLINE_FOR_ ## S ++; } }#define INCLUDE_LIBRARY#include __FILE__#endif // INCLUDE_LIBRARY#endif // INCLUDE_SUB#endif // INCLUDE_MAIN