#911044 (C++17) No.2495 Three Sets

提出ソース

結果

問題	No.2495 Three Sets
ユーザー	👑 p-adic
提出日時	2023-09-05 14:49:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	507 ms / 3,000 ms
コード長	10,739 bytes
コンパイル時間	3,402 ms
コンパイル使用メモリ	227,316 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-24 03:11:37
合計ジャッジ時間	6,724 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	3 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	6 ms 6,940 KB
testcase_12	AC	12 ms 6,944 KB
testcase_13	AC	431 ms 6,940 KB
testcase_14	AC	478 ms 6,944 KB
testcase_15	AC	438 ms 6,944 KB
testcase_16	AC	507 ms 6,944 KB
testcase_17	AC	502 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	29 ms 6,940 KB
testcase_20	AC	26 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) 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 RETURN( ANSWER ) COUT( ( ANSWER ) ); QUIT

#ifdef DEBUG
  inline 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; int VARIABLE_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 ) != " " ); string VARIABLE_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 ); int VARIABLE_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 );
  CEXPR( int , bound_ABC , 3000 ); // 0が3個
  int N[3] = { N_A , N_B , N_C };
  int length_ABC[3] = { 1 , 1 , 1 };
  int S_ABC[3][bound_ABC*2+2] = { { 0 } , { 0 } , { 0 } };
  ll ABC_sum[3][bound_ABC*2+2] = { { 0 } , { 0 } , { 0 } };
  int C_sort[bound_ABC*2+2] = { bound_ABC };
  FOR( n , 0 , 3 ){
    int& Nn = N[n];
    int& length_An = length_ABC[n];
    auto& S_An = S_ABC[n];
    auto& An_sum = ABC_sum[n];
    map<int,int> An{};
    An[-bound_ABC];
    REPEAT( Nn ){
      CIN_ASSERT( Ani , -bound_ABC , bound_ABC );
      An[-Ani]++;
    }
    FOR_ITR( An ){
      const int& Ani = itr_An->first;
      int& count_Ani = itr_An->second ;
      S_An[length_An] = S_An[length_An - 1] + count_Ani;
      An_sum[length_An] = An_sum[length_An - 1] - Ani * count_Ani;
      if( n == 2 ){
	C_sort[length_An] = -Ani;
      }
      length_An++;
    }
  }
  CHECK_REDUNDANT_INPUT;
  ll answer = 0;
  auto& S_A = S_ABC[0];
  auto& S_B = S_ABC[1];
  auto& S_C = S_ABC[2];
  auto& A_sum = ABC_sum[0];
  auto& B_sum = ABC_sum[1];
  auto& C_sum = ABC_sum[2];
  int& length_A = length_ABC[0];
  int& length_B = length_ABC[1];
  int& length_C = length_ABC[2];
  int BS[bound_ABC*2+1];
  FOREQ( x , -bound_ABC , bound_ABC ){
    BS3( k , 0 , length_C - 1 , C_sort[k] , x );
    BS[x+bound_ABC] = k;
  }
  FOR( i , 0 , length_A ){
    int& S_A_i = S_A[i];
    ll& A_sum_i = A_sum[i];
    FOR( j , 0 , length_B ){
      int& S_B_j = S_B[j];
      ll& B_sum_j = B_sum[j];
      if( B_sum_j + bound_ABC * S_A_i < 0 ){
	continue;
      }
      int k;
      if( S_A_i == 0 ){
	k = length_C - 1;
      } else {
	ll x = - ( B_sum_j / S_A_i ) + bound_ABC;
	x < 0 ? x = 0 : x;
	k = x <= bound_ABC * 2 ? BS[x] : 0;
      }
      if( k > 0 ){
	ll temp = A_sum_i * S_B_j + B_sum_j * S_C[k] + C_sum[k] * S_A_i;
	answer < temp ? answer = temp : answer;
      }
    }
  }
  RETURN( answer );
}

yukicoder

結果

テストケース

ソースコード