test/yukicoder/409.LARSCH.test.cpp

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

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• 簡易版LARSCH (src/Optimization/simplified_larsch_dp.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/409
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#include "src/Optimization/simplified_larsch_dp.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 long long N, A, B, W;
 cin >> N >> A >> B >> W;
 long long D[N];
 for (int i= 0; i < N; ++i) cin >> D[i];
 auto w= [&](int i, int j) { return D[i - 1] + B * (i - j) * (i - j - 1) / 2 - A * (i - j - 1); };
 auto dp= simplified_larsch_dp(N, w);
 long long ans= 1e18;
 for (int i= 0; i <= N; ++i) ans= min(ans, dp[i] + B * (N - i) * (N - i + 1) / 2 - A * (N - i));
 cout << ans + W << '\n';
 return 0;
}

#line 1 "test/yukicoder/409.LARSCH.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/409
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#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 7 "test/yukicoder/409.LARSCH.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 long long N, A, B, W;
 cin >> N >> A >> B >> W;
 long long D[N];
 for (int i= 0; i < N; ++i) cin >> D[i];
 auto w= [&](int i, int j) { return D[i - 1] + B * (i - j) * (i - j - 1) / 2 - A * (i - j - 1); };
 auto dp= simplified_larsch_dp(N, w);
 long long ans= 1e18;
 for (int i= 0; i <= N; ++i) ans= min(ans, dp[i] + B * (N - i) * (N - i + 1) / 2 - A * (N - i));
 cout << ans + W << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	1smallsmall01.txt	AC	6 ms	4 MB
g++-13	1smallsmall02.txt	AC	6 ms	4 MB
g++-13	1smallsmall03.txt	AC	6 ms	4 MB
g++-13	1smallsmall04.txt	AC	6 ms	4 MB
g++-13	1smallsmall05.txt	AC	6 ms	4 MB
g++-13	1smallsmall06.txt	AC	5 ms	4 MB
g++-13	1smallsmall07.txt	AC	5 ms	4 MB
g++-13	1smallsmall08.txt	AC	5 ms	4 MB
g++-13	1smallsmall09.txt	AC	5 ms	4 MB
g++-13	1smallsmall10.txt	AC	5 ms	4 MB
g++-13	1smallsmall11.txt	AC	5 ms	4 MB
g++-13	1smallsmall12.txt	AC	5 ms	4 MB
g++-13	1smallsmall13.txt	AC	5 ms	4 MB
g++-13	1smallsmall14.txt	AC	6 ms	4 MB
g++-13	1smallsmall15.txt	AC	6 ms	4 MB
g++-13	1smallsmall16.txt	AC	5 ms	4 MB
g++-13	1smallsmall17.txt	AC	5 ms	4 MB
g++-13	1smallsmall18.txt	AC	5 ms	3 MB
g++-13	1smallsmall19.txt	AC	5 ms	4 MB
g++-13	1smallsmall20.txt	AC	5 ms	4 MB
g++-13	2smalllarge01.txt	AC	5 ms	4 MB
g++-13	2smalllarge02.txt	AC	5 ms	3 MB
g++-13	2smalllarge03.txt	AC	5 ms	4 MB
g++-13	2smalllarge04.txt	AC	5 ms	4 MB
g++-13	2smalllarge05.txt	AC	5 ms	4 MB
g++-13	2smalllarge06.txt	AC	6 ms	4 MB
g++-13	2smalllarge07.txt	AC	6 ms	4 MB
g++-13	2smalllarge08.txt	AC	6 ms	4 MB
g++-13	2smalllarge09.txt	AC	6 ms	4 MB
g++-13	2smalllarge10.txt	AC	5 ms	4 MB
g++-13	2smalllarge11.txt	AC	5 ms	3 MB
g++-13	2smalllarge12.txt	AC	5 ms	4 MB
g++-13	2smalllarge13.txt	AC	6 ms	4 MB
g++-13	2smalllarge14.txt	AC	5 ms	4 MB
g++-13	2smalllarge15.txt	AC	5 ms	4 MB
g++-13	3middle01.txt	AC	5 ms	4 MB
g++-13	3middle02.txt	AC	5 ms	4 MB
g++-13	3middle03.txt	AC	6 ms	4 MB
g++-13	3middle04.txt	AC	5 ms	4 MB
g++-13	3middle05.txt	AC	5 ms	4 MB
g++-13	3middle06.txt	AC	6 ms	4 MB
g++-13	3middle07.txt	AC	6 ms	4 MB
g++-13	3middle08.txt	AC	5 ms	4 MB
g++-13	3middle09.txt	AC	6 ms	4 MB
g++-13	3middle10.txt	AC	6 ms	4 MB
g++-13	3middle11.txt	AC	5 ms	4 MB
g++-13	3middle12.txt	AC	6 ms	4 MB
g++-13	3middle13.txt	AC	6 ms	4 MB
g++-13	3middle14.txt	AC	5 ms	4 MB
g++-13	3middle15.txt	AC	6 ms	4 MB
g++-13	3middle16.txt	AC	6 ms	4 MB
g++-13	3middle17.txt	AC	6 ms	4 MB
g++-13	3middle18.txt	AC	6 ms	4 MB
g++-13	3middle19.txt	AC	6 ms	4 MB
g++-13	3middle20.txt	AC	6 ms	4 MB
g++-13	4largesmall01.txt	AC	18 ms	7 MB
g++-13	4largesmall02.txt	AC	27 ms	11 MB
g++-13	4largesmall03.txt	AC	31 ms	11 MB
g++-13	4largesmall04.txt	AC	17 ms	7 MB
g++-13	4largesmall05.txt	AC	22 ms	8 MB
g++-13	4largesmall06.txt	AC	15 ms	6 MB
g++-13	4largesmall07.txt	AC	28 ms	10 MB
g++-13	4largesmall08.txt	AC	29 ms	11 MB
g++-13	4largesmall09.txt	AC	28 ms	10 MB
g++-13	4largesmall10.txt	AC	18 ms	7 MB
g++-13	4largesmall11.txt	AC	31 ms	10 MB
g++-13	4largesmall12.txt	AC	32 ms	11 MB
g++-13	4largesmall13.txt	AC	25 ms	9 MB
g++-13	4largesmall14.txt	AC	22 ms	8 MB
g++-13	4largesmall15.txt	AC	28 ms	10 MB
g++-13	5largelarge01.txt	AC	28 ms	10 MB
g++-13	5largelarge02.txt	AC	18 ms	7 MB
g++-13	5largelarge03.txt	AC	32 ms	11 MB
g++-13	5largelarge04.txt	AC	33 ms	10 MB
g++-13	5largelarge05.txt	AC	22 ms	8 MB
g++-13	5largelarge06.txt	AC	32 ms	10 MB
g++-13	5largelarge07.txt	AC	24 ms	8 MB
g++-13	5largelarge08.txt	AC	19 ms	7 MB
g++-13	5largelarge09.txt	AC	19 ms	7 MB
g++-13	5largelarge10.txt	AC	16 ms	6 MB
g++-13	5largelarge11.txt	AC	30 ms	11 MB
g++-13	5largelarge12.txt	AC	32 ms	10 MB
g++-13	5largelarge13.txt	AC	24 ms	9 MB
g++-13	5largelarge14.txt	AC	27 ms	9 MB
g++-13	5largelarge15.txt	AC	24 ms	8 MB
g++-13	99_system_test1.txt	AC	8 ms	4 MB
g++-13	99_system_test2.txt	AC	22 ms	8 MB
g++-13	99_system_test3.txt	AC	29 ms	10 MB
g++-13	system_test1.txt	AC	15 ms	6 MB
g++-13	system_test2.txt	AC	27 ms	9 MB
g++-13	system_test3.txt	AC	15 ms	6 MB
g++-13	system_test4.txt	AC	28 ms	9 MB
clang++-18	1smallsmall01.txt	AC	6 ms	4 MB
clang++-18	1smallsmall02.txt	AC	5 ms	4 MB
clang++-18	1smallsmall03.txt	AC	5 ms	4 MB
clang++-18	1smallsmall04.txt	AC	5 ms	4 MB
clang++-18	1smallsmall05.txt	AC	5 ms	4 MB
clang++-18	1smallsmall06.txt	AC	5 ms	4 MB
clang++-18	1smallsmall07.txt	AC	5 ms	4 MB
clang++-18	1smallsmall08.txt	AC	5 ms	4 MB
clang++-18	1smallsmall09.txt	AC	5 ms	4 MB
clang++-18	1smallsmall10.txt	AC	5 ms	4 MB
clang++-18	1smallsmall11.txt	AC	5 ms	4 MB
clang++-18	1smallsmall12.txt	AC	5 ms	4 MB
clang++-18	1smallsmall13.txt	AC	5 ms	4 MB
clang++-18	1smallsmall14.txt	AC	5 ms	4 MB
clang++-18	1smallsmall15.txt	AC	5 ms	4 MB
clang++-18	1smallsmall16.txt	AC	5 ms	4 MB
clang++-18	1smallsmall17.txt	AC	5 ms	4 MB
clang++-18	1smallsmall18.txt	AC	5 ms	4 MB
clang++-18	1smallsmall19.txt	AC	5 ms	4 MB
clang++-18	1smallsmall20.txt	AC	5 ms	4 MB
clang++-18	2smalllarge01.txt	AC	5 ms	4 MB
clang++-18	2smalllarge02.txt	AC	5 ms	4 MB
clang++-18	2smalllarge03.txt	AC	5 ms	4 MB
clang++-18	2smalllarge04.txt	AC	5 ms	4 MB
clang++-18	2smalllarge05.txt	AC	5 ms	4 MB
clang++-18	2smalllarge06.txt	AC	5 ms	4 MB
clang++-18	2smalllarge07.txt	AC	5 ms	4 MB
clang++-18	2smalllarge08.txt	AC	5 ms	4 MB
clang++-18	2smalllarge09.txt	AC	5 ms	4 MB
clang++-18	2smalllarge10.txt	AC	5 ms	4 MB
clang++-18	2smalllarge11.txt	AC	5 ms	4 MB
clang++-18	2smalllarge12.txt	AC	5 ms	4 MB
clang++-18	2smalllarge13.txt	AC	5 ms	4 MB
clang++-18	2smalllarge14.txt	AC	5 ms	4 MB
clang++-18	2smalllarge15.txt	AC	5 ms	4 MB
clang++-18	3middle01.txt	AC	5 ms	4 MB
clang++-18	3middle02.txt	AC	5 ms	4 MB
clang++-18	3middle03.txt	AC	5 ms	4 MB
clang++-18	3middle04.txt	AC	5 ms	4 MB
clang++-18	3middle05.txt	AC	5 ms	4 MB
clang++-18	3middle06.txt	AC	5 ms	4 MB
clang++-18	3middle07.txt	AC	5 ms	4 MB
clang++-18	3middle08.txt	AC	5 ms	4 MB
clang++-18	3middle09.txt	AC	5 ms	4 MB
clang++-18	3middle10.txt	AC	5 ms	4 MB
clang++-18	3middle11.txt	AC	5 ms	4 MB
clang++-18	3middle12.txt	AC	5 ms	4 MB
clang++-18	3middle13.txt	AC	5 ms	4 MB
clang++-18	3middle14.txt	AC	5 ms	4 MB
clang++-18	3middle15.txt	AC	5 ms	4 MB
clang++-18	3middle16.txt	AC	5 ms	4 MB
clang++-18	3middle17.txt	AC	5 ms	4 MB
clang++-18	3middle18.txt	AC	5 ms	4 MB
clang++-18	3middle19.txt	AC	5 ms	4 MB
clang++-18	3middle20.txt	AC	5 ms	4 MB
clang++-18	4largesmall01.txt	AC	17 ms	7 MB
clang++-18	4largesmall02.txt	AC	26 ms	11 MB
clang++-18	4largesmall03.txt	AC	29 ms	11 MB
clang++-18	4largesmall04.txt	AC	16 ms	7 MB
clang++-18	4largesmall05.txt	AC	21 ms	8 MB
clang++-18	4largesmall06.txt	AC	15 ms	6 MB
clang++-18	4largesmall07.txt	AC	27 ms	10 MB
clang++-18	4largesmall08.txt	AC	28 ms	11 MB
clang++-18	4largesmall09.txt	AC	29 ms	10 MB
clang++-18	4largesmall10.txt	AC	17 ms	7 MB
clang++-18	4largesmall11.txt	AC	30 ms	10 MB
clang++-18	4largesmall12.txt	AC	30 ms	11 MB
clang++-18	4largesmall13.txt	AC	24 ms	9 MB
clang++-18	4largesmall14.txt	AC	20 ms	8 MB
clang++-18	4largesmall15.txt	AC	27 ms	10 MB
clang++-18	5largelarge01.txt	AC	27 ms	10 MB
clang++-18	5largelarge02.txt	AC	18 ms	7 MB
clang++-18	5largelarge03.txt	AC	32 ms	11 MB
clang++-18	5largelarge04.txt	AC	32 ms	10 MB
clang++-18	5largelarge05.txt	AC	21 ms	8 MB
clang++-18	5largelarge06.txt	AC	32 ms	10 MB
clang++-18	5largelarge07.txt	AC	25 ms	8 MB
clang++-18	5largelarge08.txt	AC	19 ms	7 MB
clang++-18	5largelarge09.txt	AC	18 ms	7 MB
clang++-18	5largelarge10.txt	AC	16 ms	6 MB
clang++-18	5largelarge11.txt	AC	30 ms	11 MB
clang++-18	5largelarge12.txt	AC	31 ms	10 MB
clang++-18	5largelarge13.txt	AC	23 ms	9 MB
clang++-18	5largelarge14.txt	AC	25 ms	9 MB
clang++-18	5largelarge15.txt	AC	22 ms	8 MB
clang++-18	99_system_test1.txt	AC	7 ms	4 MB
clang++-18	99_system_test2.txt	AC	21 ms	8 MB
clang++-18	99_system_test3.txt	AC	27 ms	10 MB
clang++-18	system_test1.txt	AC	14 ms	6 MB
clang++-18	system_test2.txt	AC	26 ms	9 MB
clang++-18	system_test3.txt	AC	14 ms	6 MB
clang++-18	system_test4.txt	AC	28 ms	9 MB

Back to top page