Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:warning: test/atcoder/abc305_ex.test.cpp

Depends on

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc305/tasks/abc305_Ex
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// https://atcoder.jp/contests/abc305/tasks/abc305_h
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include "src/Optimization/fibonacci_search.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, X, base= 0;
 cin >> N >> X;
 vector<pair<int, int>> AB;
 for (int i= 0; i < N; ++i) {
  int A, B;
  cin >> A >> B;
  if (A == 1) X-= B, base+= B;
  else AB.emplace_back(A, B);
 }
 N= AB.size();
 if (N == 0) return cout << 1 << " " << base << '\n', 0;
 auto comp= [&](const pair<int, int> &l, const pair<int, int> &r) { return (long long)l.second * (r.first - 1) < (long long)r.second * (l.first - 1); };
 vector<int> w[N];
 for (int i= 0; i < N; ++i) {
  vector<pair<int, int>> s;
  for (int j= i; j < N; ++j) {
   s.emplace_back(AB[j]);
   for (int k= s.size(); --k;) {
    if (comp(s[k - 1], s[k])) break;
    swap(s[k - 1], s[k]);
   }
   long long x= 0;
   for (auto &c: s) x= c.first * x + c.second;
   if (x > X) break;
   w[i].push_back(x);
  }
 }
 auto f= [&](long long p) {
  long long dp[N + 1];
  fill_n(dp, N + 1, 1e18);
  dp[0]= 0;
  for (int i= 0; i < N; ++i)
   for (int j= 0, e= w[i].size(); j < e; ++j) dp[i + j + 1]= min(dp[i + j + 1], dp[i] + w[i][j] + p);
  return dp[N];
 };
 auto g= [&](long long p) { return (long double)(f(p) - X) / p; };
 auto [p, DD]= fibonacci_search<MAXIMIZE>(g, 1, X);
 long long D= ceil(DD);
 cout << D << " " << f(p) - p * D + base << '\n';
 return 0;
}
#line 1 "test/atcoder/abc305_ex.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc305/tasks/abc305_Ex
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// https://atcoder.jp/contests/abc305/tasks/abc305_h
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#line 3 "src/Optimization/fibonacci_search.hpp"
#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 11 "test/atcoder/abc305_ex.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, X, base= 0;
 cin >> N >> X;
 vector<pair<int, int>> AB;
 for (int i= 0; i < N; ++i) {
  int A, B;
  cin >> A >> B;
  if (A == 1) X-= B, base+= B;
  else AB.emplace_back(A, B);
 }
 N= AB.size();
 if (N == 0) return cout << 1 << " " << base << '\n', 0;
 auto comp= [&](const pair<int, int> &l, const pair<int, int> &r) { return (long long)l.second * (r.first - 1) < (long long)r.second * (l.first - 1); };
 vector<int> w[N];
 for (int i= 0; i < N; ++i) {
  vector<pair<int, int>> s;
  for (int j= i; j < N; ++j) {
   s.emplace_back(AB[j]);
   for (int k= s.size(); --k;) {
    if (comp(s[k - 1], s[k])) break;
    swap(s[k - 1], s[k]);
   }
   long long x= 0;
   for (auto &c: s) x= c.first * x + c.second;
   if (x > X) break;
   w[i].push_back(x);
  }
 }
 auto f= [&](long long p) {
  long long dp[N + 1];
  fill_n(dp, N + 1, 1e18);
  dp[0]= 0;
  for (int i= 0; i < N; ++i)
   for (int j= 0, e= w[i].size(); j < e; ++j) dp[i + j + 1]= min(dp[i + j + 1], dp[i] + w[i][j] + p);
  return dp[N];
 };
 auto g= [&](long long p) { return (long double)(f(p) - X) / p; };
 auto [p, DD]= fibonacci_search<MAXIMIZE>(g, 1, X);
 long long D= ceil(DD);
 cout << D << " " << f(p) - p * D + base << '\n';
 return 0;
}
Back to top page