結果

問題 No.705 ゴミ拾い Hard
ユーザー lumc_lumc_
提出日時 2019-01-26 02:44:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 7,662 bytes
コンパイル時間 1,467 ms
コンパイル使用メモリ 123,172 KB
実行使用メモリ 12,868 KB
最終ジャッジ日時 2024-09-16 04:53:49
合計ジャッジ時間 8,693 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 4 ms
5,376 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 RE -
testcase_24 AC 140 ms
12,520 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 AC 122 ms
12,624 KB
testcase_32 AC 118 ms
12,580 KB
testcase_33 AC 55 ms
12,548 KB
testcase_34 AC 56 ms
12,532 KB
testcase_35 AC 108 ms
12,544 KB
testcase_36 AC 114 ms
12,616 KB
testcase_37 AC 105 ms
12,636 KB
testcase_38 AC 115 ms
12,500 KB
testcase_39 RE -
testcase_40 AC 2 ms
5,376 KB
testcase_41 AC 2 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 134 ms
12,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
template < class T > ostream &operator<<(ostream &o, const stack<T> &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; }
template <class T, class Container, class Compare > ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
template <class T, class Container > ostream &operator<<(ostream &os, queue<T, Container> a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T > inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << endl; }
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
#define dump1D(...) (42)
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}

constexpr int N = 3e5;
int n;
ll a[N];
ll x[N];
ll y[N];

// D(0) is given
// D(i) = f( min(0 <= j < i,  D(j) + w(j, i)) , i)
// w must satisfy Convex QI
// by default, f is identity function
// Convex QI Speedup {{{
#include <type_traits>
#include <vector>
#include <stack>
#include <cassert>
#include <functional>
template < class T, class W, class F = function< T(const T &) > >
auto ConvexQISpeedup(T d0, size_t n, const W &w,
                     const F &f = [](const T &t) { return t; }) {
#ifdef DEBUG
  static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)");
  static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)");
#endif

  vector< T > D(n + 1);
  D[0] = d0;

  // C(j, i) = D(j) + w(j, i)
  auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); };

  // search the first time to choose l rather than k
  // if w satisfies Closest Zero Property, you can speedup h
  auto h = [&](size_t l, size_t k) {
    assert(l < k && k < n + 1);
    size_t ok = n + 1, ng = k;
    while(ok - ng > 1) {
      size_t mid = (ok + ng) >> 1;
      if(C(l, mid) <= C(k, mid))
        ok = mid;
      else
        ng = mid;
    }
    return ok;
  };

  // (k, h) where k is index and h is the time to die
  stack< pair< size_t, size_t > > S;
  S.emplace(0, n + 1);
  for(size_t i = 1; i <= n; i++) {
    size_t j = S.top().first;
    if(C(i - 1, i) >= C(j, i))
      D[i] = f(C(j, i));
    else {
      D[i] = f(C(i - 1, i));
      while(S.size() &&
            C(i - 1, S.top().second - 1) < C(S.top().first, S.top().second - 1))
        S.pop();
      if(S.empty())
        S.emplace(i - 1, n + 1);
      else
        S.emplace(j, h(S.top().first, i - 1));
    }
    if(S.top().second == i + 1) S.pop();
  }
  return D;
}
// }}}

// D(0) is given
// D(i) = f( min(0 <= j < i,  D(j) + w(j, i)) , i)
// w must satisfy Concave QI = Monge
// by default, f is identity function
// Concave QI ( = Monge ) Speedup {{{
#include <type_traits>
#include <vector>
#include <deque>
#include <cassert>
#include <functional>
template < class T, class W, class F = function< T(const T &) > >
auto ConcaveQISpeedup(T d0, size_t n, const W &w,
                      const F &f = [](const T &t) { return t; }) {
#ifdef DEBUG
  static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)");
  static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)");
#endif

  vector< T > D(n + 1);
  D[0] = d0;

  // C(j, i) = D(j) + w(j, i)
  auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); };

  // search the first time to choose l rather than k
  // if w satisfies Closest Zero Property, you can speedup h
  auto h = [&](size_t l, size_t k) {
    assert(k < l && l < n + 1);
    size_t ok = n + 1, ng = l;
    while(ok - ng > 1) {
      size_t mid = (ok + ng) >> 1;
      if(C(l, mid) <= C(k, mid))
        ok = mid;
      else
        ng = mid;
    }
    return ok;
  };

  // (k, h) where k is index and h is the time to kill predecessor
  deque< pair< size_t, size_t > > Q;
  Q.emplace_back(0, 1);
  for(size_t i = 1; i <= n; i++) {
    assert(Q.size());
    size_t j = Q.front().first;
    if(C(i - 1, i) <= C(j, i)) {
      D[i] = f(C(i - 1, i));
      Q.clear();
      Q.emplace_back(i - 1, i + 1);
    } else {
      D[i] = f(C(j, i));
      while(Q.size() > 1 &&
            C(i - 1, Q.back().second) <= C(Q.back().first, Q.back().second))
        Q.pop_back();
      size_t k = h(i - 1, Q.back().first);
      if(k < n + 1) Q.emplace_back(i - 1, k);
      if(i + 1 == Q[1].second)
        Q.pop_front();
      else
        Q.front().second++;
    }
  }
  return D;
}
// }}}

#if 0
#convex QIについて
l < kについて "kではなくl ( = 小さい方) を選ぶ利点" はだんだん大きくなる

C(j, i) は i から j を選ぶときの損 のように考えればよい (損を最小化する)

#endif

constexpr ll inf = 1e18;

inline ll pow3(ll x) { return x * x * x; }

// 1-indexed
ll g(int k, int i) {
  assert(k < i);
  return pow3(abs(x[k] - a[i - 1])) + pow3(y[k]);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> x[i];
  for(int i = 0; i < n; i++) cin >> y[i];

  cout << ConcaveQISpeedup< ll >(0, n, g)[n] << endl;
  return 0;
}
0