結果
問題 | No.2495 Three Sets |
ユーザー |
👑 |
提出日時 | 2023-09-05 20:11:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 9,947 bytes |
コンパイル時間 | 3,157 ms |
コンパイル使用メモリ | 219,992 KB |
最終ジャッジ日時 | 2025-02-16 18:52:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 7 WA * 11 |
ソースコード
// 愚直解(N_A N_B N_C 2^{N_A+N_B+N_C})チェック#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( MESSAGE ) cerr << MESSAGE << 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 ) )#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( MESSAGE )#define COUT( ANSWER ) cout << ANSWER << "\n"#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )#endif#include <bits/stdc++.h>using namespace std;using uint = unsigned int;using ll = long long;using ull = unsigned long long;#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 SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_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 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 RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT#ifdef DEBUGinline void AlertAbort( int n ) { CERR("abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }#endif// 二分探索テンプレート// 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<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 ) \// 入力フォーマットチェック用// 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#define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert(VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin )// #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 )#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 ++; } }int main(){UNTIE;DEXPR( int , bound_N , 100000 , 100 ); // 0が5個CIN_ASSERT( N_A , 1 , bound_N );CIN_ASSERT( N_B , 1 , bound_N );CIN_ASSERT( N_C , 1 , bound_N );if( N_A > 62 || N_B > 62 || N_C > 62 ){RETURN( "愚直解では計算できません。" );}int A[N_A];FOR( i , 0 , N_A ){cin >> A[i];}int B[N_B];FOR( j , 0 , N_B ){cin >> B[j];}int C[N_C];FOR( k , 0 , N_C ){cin >> C[k];}ll answer = 0;ll power_N_A = 1ULL << N_A;ll power_N_B = 1ULL << N_B;ll power_N_C = 1ULL << N_C;FOR( S_A , 0 , power_N_A ){int count_A = 0;ll A_sum = 0;FOR( i , 0 , N_A ){if( ( ( S_A >> i ) & 1 ) == 1 ){count_A++;A_sum += A[i];}}FOR( S_B , 0 , power_N_B ){int count_B = 0;ll B_sum = 0;FOR( j , 0 , N_B ){if( ( ( S_B >> j ) & 1 ) == 1 ){count_B++;B_sum += B[j];}}FOR( S_C , 0 , power_N_C ){int count_C = 0;ll C_sum = 0;FOR( k , 0 , N_C ){if( ( ( S_C >> k ) & 1 ) == 1 ){count_C++;C_sum += C[k];}}ll temp = A_sum * count_B + B_sum * count_C + C_sum * count_A;if( answer < temp ){CERR( "(S_A,S_B,S_C) = (" << S_A << "," << S_B << "," << S_C << ")" );answer = temp;}}}}RETURN( answer );}