test/aoj/2603.AlienDP.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 10:56:39+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2603

Depends on

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

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2603
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// Alien DP
#include <iostream>
#include <algorithm>
#include "src/Optimization/simplified_larsch_dp.hpp"
#include "src/Optimization/fibonacci_search.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int s, n, m;
 cin >> s >> n >> m;
 int x[s];
 for (int i= 0; i < s; ++i) cin >> x[i];
 int a[n];
 for (int i= 0; i < n; ++i) {
  int t, p;
  cin >> t >> p;
  a[i]= t - x[p - 1];
 }
 if (n <= m) return cout << 0 << '\n', 0;
 sort(a, a + n);
 int sum[n + 1];
 sum[0]= 0;
 for (int i= 0; i < n; ++i) sum[i + 1]= sum[i] + a[i];
 auto w= [&](int i, int j) { return (i - j) * a[i - 1] - (sum[i] - sum[j]); };

 auto f= [&](int p) {
  auto ww= [&](int i, int j) { return w(i, j) + p; };
  auto dp= simplified_larsch_dp(n, ww);
  return dp[n] - p * m;
 };
 auto [_, ans]= fibonacci_search<MAXIMIZE>(f, -3e5, 3e5);
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/2603.AlienDP.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2603
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// Alien DP
#include <iostream>
#include <algorithm>
#line 2 "src/Optimization/simplified_larsch_dp.hpp"
#include <vector>
#include <limits>
#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 5 "src/Optimization/simplified_larsch_dp.hpp"
// dp[i] = min_{j<i} (dp[j] + w(i,j))
// w(i,j) -> monge cost
template <class F> std::vector<result_type_t<F>> simplified_larsch_dp(int n, const F &w) {
 using T= result_type_t<F>;
 std::vector<T> dp(n + 1, std::numeric_limits<T>::max());
 std::vector<int> x(n + 1);
 auto check= [&](int i, int j) {
  if (T cost= dp[j] + w(i, j); dp[i] > cost) dp[i]= cost, x[i]= j;
 };
 auto rec= [&](auto &rec, int l, int r) {
  if (r - l <= 1) return;
  int m= (l + r) / 2;
  for (int i= x[l]; i <= x[r]; ++i) check(m, i);
  rec(rec, l, m);
  for (int i= l + 1; i <= m; ++i) check(r, i);
  rec(rec, m, r);
 };
 return dp[0]= 0, check(n, 0), rec(rec, 0, n), dp;
}
#line 3 "src/Optimization/fibonacci_search.hpp"
#include <cassert>
#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 9 "test/aoj/2603.AlienDP.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int s, n, m;
 cin >> s >> n >> m;
 int x[s];
 for (int i= 0; i < s; ++i) cin >> x[i];
 int a[n];
 for (int i= 0; i < n; ++i) {
  int t, p;
  cin >> t >> p;
  a[i]= t - x[p - 1];
 }
 if (n <= m) return cout << 0 << '\n', 0;
 sort(a, a + n);
 int sum[n + 1];
 sum[0]= 0;
 for (int i= 0; i < n; ++i) sum[i + 1]= sum[i] + a[i];
 auto w= [&](int i, int j) { return (i - j) * a[i - 1] - (sum[i] - sum[j]); };

 auto f= [&](int p) {
  auto ww= [&](int i, int j) { return w(i, j) + p; };
  auto dp= simplified_larsch_dp(n, ww);
  return dp[n] - p * m;
 };
 auto [_, ans]= fibonacci_search<MAXIMIZE>(f, -3e5, 3e5);
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.txt	AC	5 ms	4 MB
g++-13	00_sample_01.txt	AC	5 ms	4 MB
g++-13	00_sample_02.txt	AC	5 ms	3 MB
g++-13	01_teuchi_00.txt	AC	5 ms	4 MB
g++-13	99_large_random_0.txt	AC	5 ms	4 MB
g++-13	99_large_random_1.txt	AC	5 ms	4 MB
g++-13	99_large_random_2.txt	AC	5 ms	4 MB
g++-13	99_large_random_3.txt	AC	5 ms	4 MB
g++-13	99_large_random_4.txt	AC	5 ms	3 MB
g++-13	99_large_random_5.txt	AC	5 ms	4 MB
g++-13	99_large_random_6.txt	AC	5 ms	4 MB
g++-13	99_large_random_7.txt	AC	5 ms	4 MB
g++-13	99_large_random_8.txt	AC	5 ms	4 MB
g++-13	99_large_random_9.txt	AC	5 ms	4 MB
g++-13	99_max_random_0.txt	AC	7 ms	4 MB
g++-13	99_max_random_1.txt	AC	7 ms	4 MB
g++-13	99_max_random_2.txt	AC	7 ms	4 MB
g++-13	99_max_random_3.txt	AC	7 ms	4 MB
g++-13	99_max_random_4.txt	AC	7 ms	4 MB
g++-13	99_max_random_5.txt	AC	7 ms	4 MB
g++-13	99_max_random_6.txt	AC	7 ms	4 MB
g++-13	99_max_random_7.txt	AC	7 ms	4 MB
g++-13	99_max_random_8.txt	AC	7 ms	4 MB
g++-13	99_max_random_9.txt	AC	7 ms	4 MB
g++-13	99_middle_random_0.txt	AC	5 ms	4 MB
g++-13	99_middle_random_1.txt	AC	5 ms	3 MB
g++-13	99_middle_random_2.txt	AC	5 ms	4 MB
g++-13	99_middle_random_3.txt	AC	5 ms	4 MB
g++-13	99_middle_random_4.txt	AC	5 ms	4 MB
g++-13	99_middle_random_5.txt	AC	5 ms	4 MB
g++-13	99_middle_random_6.txt	AC	5 ms	3 MB
g++-13	99_middle_random_7.txt	AC	5 ms	4 MB
g++-13	99_middle_random_8.txt	AC	5 ms	3 MB
g++-13	99_middle_random_9.txt	AC	5 ms	4 MB
g++-13	99_small_random_0.txt	AC	5 ms	4 MB
g++-13	99_small_random_1.txt	AC	5 ms	4 MB
g++-13	99_small_random_2.txt	AC	5 ms	4 MB
g++-13	99_small_random_3.txt	AC	5 ms	4 MB
g++-13	99_small_random_4.txt	AC	5 ms	4 MB
g++-13	99_small_random_5.txt	AC	5 ms	4 MB
g++-13	99_small_random_6.txt	AC	5 ms	4 MB
g++-13	99_small_random_7.txt	AC	5 ms	4 MB
g++-13	99_small_random_8.txt	AC	5 ms	4 MB
g++-13	99_small_random_9.txt	AC	5 ms	3 MB
g++-13	99_tiny_random_0.txt	AC	5 ms	3 MB
g++-13	99_tiny_random_1.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_2.txt	AC	4 ms	4 MB
g++-13	99_tiny_random_3.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_4.txt	AC	5 ms	3 MB
g++-13	99_tiny_random_5.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_6.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_7.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_8.txt	AC	5 ms	4 MB
g++-13	99_tiny_random_9.txt	AC	5 ms	4 MB
clang++-18	00_sample_00.txt	AC	5 ms	4 MB
clang++-18	00_sample_01.txt	AC	5 ms	4 MB
clang++-18	00_sample_02.txt	AC	5 ms	4 MB
clang++-18	01_teuchi_00.txt	AC	5 ms	4 MB
clang++-18	99_large_random_0.txt	AC	5 ms	4 MB
clang++-18	99_large_random_1.txt	AC	5 ms	4 MB
clang++-18	99_large_random_2.txt	AC	5 ms	4 MB
clang++-18	99_large_random_3.txt	AC	5 ms	4 MB
clang++-18	99_large_random_4.txt	AC	5 ms	4 MB
clang++-18	99_large_random_5.txt	AC	5 ms	4 MB
clang++-18	99_large_random_6.txt	AC	5 ms	4 MB
clang++-18	99_large_random_7.txt	AC	5 ms	4 MB
clang++-18	99_large_random_8.txt	AC	5 ms	4 MB
clang++-18	99_large_random_9.txt	AC	5 ms	4 MB
clang++-18	99_max_random_0.txt	AC	7 ms	4 MB
clang++-18	99_max_random_1.txt	AC	7 ms	4 MB
clang++-18	99_max_random_2.txt	AC	7 ms	4 MB
clang++-18	99_max_random_3.txt	AC	7 ms	4 MB
clang++-18	99_max_random_4.txt	AC	7 ms	4 MB
clang++-18	99_max_random_5.txt	AC	7 ms	4 MB
clang++-18	99_max_random_6.txt	AC	7 ms	4 MB
clang++-18	99_max_random_7.txt	AC	7 ms	4 MB
clang++-18	99_max_random_8.txt	AC	6 ms	4 MB
clang++-18	99_max_random_9.txt	AC	7 ms	4 MB
clang++-18	99_middle_random_0.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_1.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_2.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_3.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_4.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_5.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_6.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_7.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_8.txt	AC	5 ms	4 MB
clang++-18	99_middle_random_9.txt	AC	5 ms	4 MB
clang++-18	99_small_random_0.txt	AC	5 ms	4 MB
clang++-18	99_small_random_1.txt	AC	5 ms	4 MB
clang++-18	99_small_random_2.txt	AC	5 ms	4 MB
clang++-18	99_small_random_3.txt	AC	5 ms	4 MB
clang++-18	99_small_random_4.txt	AC	4 ms	4 MB
clang++-18	99_small_random_5.txt	AC	5 ms	4 MB
clang++-18	99_small_random_6.txt	AC	5 ms	4 MB
clang++-18	99_small_random_7.txt	AC	4 ms	4 MB
clang++-18	99_small_random_8.txt	AC	5 ms	4 MB
clang++-18	99_small_random_9.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_0.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_1.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_2.txt	AC	4 ms	4 MB
clang++-18	99_tiny_random_3.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_4.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_5.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_6.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_7.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_8.txt	AC	5 ms	4 MB
clang++-18	99_tiny_random_9.txt	AC	5 ms	4 MB

Back to top page