test/yukicoder/2309.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/2309

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• フィボナッチ探索 (src/Optimization/fibonacci_search.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2309
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/Optimization/fibonacci_search.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int T;
 cin >> T;
 for (; T--;) {
  int A, B, C, X, Y, Z, W;
  cin >> A >> B >> C >> X >> Y >> Z >> W;
  long long ans= 0;
  for (int a= min(A, B) + 1; a--;) {
   auto f= [&](int b) {
    long long D= min(A - a, C - b), E= B - a - b, F= min(D, E);
    return D * Z + F * max(0, W - Z) + (long long)b * Y + (long long)a * X;
   };
   auto [x, fx]= fibonacci_search<MAXIMIZE>(f, 0, min(B - a, C));
   ans= max(ans, fx);
  }
  cout << ans << '\n';
 }
 return 0;
}

#line 1 "test/yukicoder/2309.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2309
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/Optimization/fibonacci_search.hpp"
#include <algorithm>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 6 "src/Optimization/fibonacci_search.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<int64_t, result_type_t<F>> fibonacci_search(const F &f, int64_t l, int64_t r) {
 assert(l <= r);
 int64_t s= 1, t= 2, a= l - 1, x, b, y;
 for (int64_t e= r - l + 2; t < e;) std::swap(s+= t, t);
 b= a + t, x= b - s;
 result_type_t<F> fx= f(x), fy;
 for (bool g; a + b != 2 * x;) {
  if (y= a + b - x; r < y) b= a, a= y;
  else {
   if constexpr (obj == MINIMIZE) g= fx < (fy= f(y));
   else g= fx > (fy= f(y));
   if (g) b= a, a= y;
   else a= x, x= y, fx= fy;
  }
 }
 return {x, fx};
}
#line 6 "test/yukicoder/2309.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int T;
 cin >> T;
 for (; T--;) {
  int A, B, C, X, Y, Z, W;
  cin >> A >> B >> C >> X >> Y >> Z >> W;
  long long ans= 0;
  for (int a= min(A, B) + 1; a--;) {
   auto f= [&](int b) {
    long long D= min(A - a, C - b), E= B - a - b, F= min(D, E);
    return D * Z + F * max(0, W - Z) + (long long)b * Y + (long long)a * X;
   };
   auto [x, fx]= fibonacci_search<MAXIMIZE>(f, 0, min(B - a, C));
   ans= max(ans, fx);
  }
  cout << ans << '\n';
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	0_Sample_1.txt	AC	8 ms	4 MB
g++-13	1_Random_1.txt	AC	28 ms	4 MB
g++-13	1_Random_10.txt	AC	21 ms	4 MB
g++-13	1_Random_11.txt	AC	25 ms	4 MB
g++-13	1_Random_12.txt	AC	28 ms	4 MB
g++-13	1_Random_13.txt	AC	29 ms	4 MB
g++-13	1_Random_14.txt	AC	23 ms	4 MB
g++-13	1_Random_15.txt	AC	27 ms	4 MB
g++-13	1_Random_16.txt	AC	17 ms	4 MB
g++-13	1_Random_17.txt	AC	31 ms	4 MB
g++-13	1_Random_18.txt	AC	29 ms	4 MB
g++-13	1_Random_19.txt	AC	22 ms	4 MB
g++-13	1_Random_2.txt	AC	27 ms	4 MB
g++-13	1_Random_20.txt	AC	27 ms	4 MB
g++-13	1_Random_21.txt	AC	16 ms	4 MB
g++-13	1_Random_22.txt	AC	18 ms	4 MB
g++-13	1_Random_23.txt	AC	21 ms	4 MB
g++-13	1_Random_24.txt	AC	28 ms	4 MB
g++-13	1_Random_25.txt	AC	26 ms	4 MB
g++-13	1_Random_26.txt	AC	32 ms	4 MB
g++-13	1_Random_27.txt	AC	21 ms	4 MB
g++-13	1_Random_28.txt	AC	21 ms	4 MB
g++-13	1_Random_29.txt	AC	29 ms	4 MB
g++-13	1_Random_3.txt	AC	24 ms	4 MB
g++-13	1_Random_30.txt	AC	28 ms	4 MB
g++-13	1_Random_4.txt	AC	22 ms	4 MB
g++-13	1_Random_5.txt	AC	23 ms	4 MB
g++-13	1_Random_6.txt	AC	19 ms	4 MB
g++-13	1_Random_7.txt	AC	21 ms	4 MB
g++-13	1_Random_8.txt	AC	28 ms	4 MB
g++-13	1_Random_9.txt	AC	30 ms	4 MB
g++-13	2_Random_Large_1.txt	AC	70 ms	4 MB
g++-13	2_Random_Large_2.txt	AC	70 ms	4 MB
g++-13	2_Random_Large_3.txt	AC	70 ms	4 MB
g++-13	2_Random_Large_4.txt	AC	68 ms	4 MB
g++-13	2_Random_Large_5.txt	AC	67 ms	4 MB
g++-13	3_Random_Exp_1.txt	AC	6 ms	4 MB
g++-13	3_Random_Exp_2.txt	AC	5 ms	4 MB
g++-13	3_Random_Exp_3.txt	AC	5 ms	4 MB
g++-13	3_Random_Exp_4.txt	AC	5 ms	4 MB
g++-13	3_Random_Exp_5.txt	AC	5 ms	4 MB
g++-13	4_Max_Random_1.txt	AC	65 ms	4 MB
g++-13	4_Max_Random_2.txt	AC	74 ms	4 MB
g++-13	5_Same_Value_1.txt	AC	27 ms	4 MB
g++-13	5_Same_Value_2.txt	AC	21 ms	4 MB
g++-13	6_Rational_1.txt	AC	26 ms	4 MB
g++-13	6_Rational_2.txt	AC	22 ms	4 MB
g++-13	7_Hand_1.txt	AC	11 ms	4 MB
g++-13	7_Hand_2.txt	AC	5 ms	4 MB
g++-13	7_Hand_3.txt	AC	6 ms	4 MB
clang++-18	0_Sample_1.txt	AC	8 ms	4 MB
clang++-18	1_Random_1.txt	AC	29 ms	4 MB
clang++-18	1_Random_10.txt	AC	22 ms	4 MB
clang++-18	1_Random_11.txt	AC	26 ms	4 MB
clang++-18	1_Random_12.txt	AC	28 ms	4 MB
clang++-18	1_Random_13.txt	AC	30 ms	4 MB
clang++-18	1_Random_14.txt	AC	24 ms	4 MB
clang++-18	1_Random_15.txt	AC	28 ms	4 MB
clang++-18	1_Random_16.txt	AC	18 ms	4 MB
clang++-18	1_Random_17.txt	AC	33 ms	4 MB
clang++-18	1_Random_18.txt	AC	30 ms	4 MB
clang++-18	1_Random_19.txt	AC	23 ms	4 MB
clang++-18	1_Random_2.txt	AC	28 ms	4 MB
clang++-18	1_Random_20.txt	AC	28 ms	4 MB
clang++-18	1_Random_21.txt	AC	18 ms	4 MB
clang++-18	1_Random_22.txt	AC	19 ms	4 MB
clang++-18	1_Random_23.txt	AC	23 ms	4 MB
clang++-18	1_Random_24.txt	AC	31 ms	4 MB
clang++-18	1_Random_25.txt	AC	27 ms	4 MB
clang++-18	1_Random_26.txt	AC	34 ms	4 MB
clang++-18	1_Random_27.txt	AC	22 ms	4 MB
clang++-18	1_Random_28.txt	AC	22 ms	4 MB
clang++-18	1_Random_29.txt	AC	31 ms	4 MB
clang++-18	1_Random_3.txt	AC	26 ms	4 MB
clang++-18	1_Random_30.txt	AC	30 ms	4 MB
clang++-18	1_Random_4.txt	AC	23 ms	4 MB
clang++-18	1_Random_5.txt	AC	24 ms	4 MB
clang++-18	1_Random_6.txt	AC	20 ms	4 MB
clang++-18	1_Random_7.txt	AC	22 ms	4 MB
clang++-18	1_Random_8.txt	AC	29 ms	4 MB
clang++-18	1_Random_9.txt	AC	31 ms	4 MB
clang++-18	2_Random_Large_1.txt	AC	71 ms	4 MB
clang++-18	2_Random_Large_2.txt	AC	71 ms	4 MB
clang++-18	2_Random_Large_3.txt	AC	72 ms	4 MB
clang++-18	2_Random_Large_4.txt	AC	70 ms	4 MB
clang++-18	2_Random_Large_5.txt	AC	69 ms	4 MB
clang++-18	3_Random_Exp_1.txt	AC	5 ms	4 MB
clang++-18	3_Random_Exp_2.txt	AC	4 ms	4 MB
clang++-18	3_Random_Exp_3.txt	AC	5 ms	4 MB
clang++-18	3_Random_Exp_4.txt	AC	5 ms	4 MB
clang++-18	3_Random_Exp_5.txt	AC	5 ms	4 MB
clang++-18	4_Max_Random_1.txt	AC	69 ms	4 MB
clang++-18	4_Max_Random_2.txt	AC	76 ms	4 MB
clang++-18	5_Same_Value_1.txt	AC	28 ms	4 MB
clang++-18	5_Same_Value_2.txt	AC	22 ms	4 MB
clang++-18	6_Rational_1.txt	AC	27 ms	4 MB
clang++-18	6_Rational_2.txt	AC	22 ms	4 MB
clang++-18	7_Hand_1.txt	AC	12 ms	4 MB
clang++-18	7_Hand_2.txt	AC	5 ms	4 MB
clang++-18	7_Hand_3.txt	AC	6 ms	4 MB

Back to top page