#842685 (C++17) No.2114 01 Matching

• 問題: No.2114 01 Matching
• ユーザー: hashiryo
• 提出日時: 2023-02-23 21:14:45
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 17,129 bytes
• コンパイル時間: 3,145 ms
• コンパイル使用メモリ: 238,524 KB
• 実行使用メモリ: 52,456 KB
• 最終ジャッジ日時: 2023-08-16 02:54:26
• 合計ジャッジ時間: 12,657 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,384 KB
testcase_01	AC	2 ms; 4,384 KB
testcase_02	AC	121 ms; 8,036 KB
testcase_03	AC	41 ms; 12,912 KB
testcase_04	AC	66 ms; 17,272 KB
testcase_05	AC	46 ms; 5,828 KB
testcase_06	AC	49 ms; 5,072 KB
testcase_07	AC	49 ms; 5,144 KB
testcase_08	AC	140 ms; 10,780 KB
testcase_09	AC	99 ms; 6,068 KB
testcase_10	AC	50 ms; 5,232 KB
testcase_11	AC	268 ms; 52,412 KB
testcase_12	AC	264 ms; 52,364 KB
testcase_13	AC	116 ms; 15,736 KB
testcase_14	AC	94 ms; 10,116 KB
testcase_15	AC	99 ms; 10,244 KB
testcase_16	AC	186 ms; 9,852 KB
testcase_17	AC	88 ms; 6,576 KB
testcase_18	AC	86 ms; 10,196 KB
testcase_19	AC	122 ms; 13,696 KB
testcase_20	AC	281 ms; 52,340 KB
testcase_21	AC	155 ms; 13,396 KB
testcase_22	AC	86 ms; 5,164 KB
testcase_23	AC	113 ms; 11,428 KB
testcase_24	AC	26 ms; 4,988 KB
testcase_25	AC	29 ms; 10,280 KB
testcase_26	AC	280 ms; 52,336 KB
testcase_27	AC	262 ms; 52,340 KB
testcase_28	AC	128 ms; 29,904 KB
testcase_29	AC	269 ms; 52,456 KB
testcase_30	AC	54 ms; 5,116 KB
testcase_31	AC	280 ms; 52,300 KB
testcase_32	AC	130 ms; 6,988 KB
testcase_33	AC	50 ms; 5,172 KB
testcase_34	AC	59 ms; 5,880 KB
testcase_35	AC	82 ms; 22,268 KB
testcase_36	AC	279 ms; 52,304 KB
testcase_37	AC	103 ms; 7,164 KB
testcase_38	AC	51 ms; 5,176 KB
testcase_39	AC	51 ms; 5,856 KB
testcase_40	AC	84 ms; 21,644 KB
testcase_41	AC	117 ms; 7,064 KB
testcase_42	AC	96 ms; 9,460 KB
testcase_43	AC	130 ms; 7,108 KB
testcase_44	AC	182 ms; 14,028 KB
testcase_45	AC	270 ms; 52,092 KB
testcase_46	AC	38 ms; 5,108 KB
testcase_47	AC	297 ms; 52,160 KB
testcase_48	AC	288 ms; 52,356 KB
testcase_49	AC	116 ms; 13,812 KB
testcase_50	AC	48 ms; 4,592 KB
testcase_51	AC	50 ms; 5,080 KB
testcase_52	WA	-

ソースコード

#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on
template <class T> auto compress(std::vector<T> &v) {
 return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
template <std::size_t NODE_SIZE= 1 << 22> class PiecewiseLinearConvexfunction {
public:
 using i64= long long;
 using i128= __int128_t;
 using node_id= std::int_least32_t;
 static constexpr i64 INF= 1ll << 41;
 template <class Int> static inline std::string str(Int x) {
  if (x >= INF) return "inf";
  if (x <= -INF) return "-inf";
  std::stringstream ss;
  ss << x;
  return ss.str();
 }
 struct Node {
  node_id ch[2], par;
  int sz;
  i64 dx, slope, laz, x;
  i128 y;
 };
 friend std::ostream &operator<<(std::ostream &os, Node *t) {
  if (!t) return os << "nullptr";
  return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << ",x:" << str(t->x) << ",y:" << str(t->y) << ",laz:" << str(t->laz) << "}";
 }
 // friend std::ostream &operator<<(std::ostream &os, Node *t) {
 //  if (!t) return os << "nullptr";
 //  return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << "}";
 // }
 static inline Node ns[NODE_SIZE];
 static inline node_id ni= 1;
 static inline void clear() { ni= 1; }
 static inline void propagate(node_id i, i64 a) {
  if (i) ns[i].slope+= a, ns[i].laz+= a, ns[i].y+= i128(a) * ns[i].x;
 }
 static inline void push(node_id i) {
  if (ns[i].laz) propagate(ns[i].ch[0], ns[i].laz), propagate(ns[i].ch[1], ns[i].laz), ns[i].laz= 0;
 }
 static inline void pushup(node_id i) {
  ns[i].sz= 1, ns[i].x= ns[i].dx, ns[i].y= i128(ns[i].slope) * ns[i].dx;
  if (int j= ns[i].ch[0]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
  if (int j= ns[i].ch[1]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
 }
 static inline int dir(node_id i) { return ns[ns[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= ns[i].par;
  int d= dir(i);
  if ((ns[p].ch[d]= ns[i].ch[!d])) ns[ns[p].ch[d]].par= p;
  ns[i].ch[!d]= p;
  if ((ns[i].par= ns[p].par)) ns[ns[p].par].ch[dir(p)]= i;
  ns[p].par= i;
 }
 static inline void splay(node_id i) {
  for (node_id p= ns[i].par; p; p= ns[i].par) {
   if (node_id pp= ns[p].par; pp) rot(dir(i) == dir(p) ? p : i), rot(i), pushup(pp), pushup(p);
   else rot(i), pushup(p);
  }
  pushup(i);
 }
 static inline void slope_search(node_id &i, i64 k) {
  for (node_id s;; i= s) {
   push(i);
   i64 tmp= ns[i].slope;
   if (tmp == k) break;
   if (s= ns[i].ch[tmp < k]; !s) break;
  }
  splay(i);
 }
 static inline void x_search(node_id &i, i64 x) {
  for (bool c;; i= ns[i].ch[c]) {
   push(i);
   i64 l= ns[i].ch[0] ? ns[ns[i].ch[0]].x : 0, r= l + ns[i].dx;
   if (l <= x && x <= r) return splay(i);
   if ((c= (r < x))) x-= r;
  }
 }
 static inline void debugoutput(node_id i, int d) {
  if (!i) return;
  push(i);
  debugoutput(ns[i].ch[0], d + 1);
  for (int i= 0; i < d; ++i) std::cerr << "   ";
  std::cerr << "■ " << (i ? ns + i : nullptr) << '\n';
  debugoutput(ns[i].ch[1], d + 1);
 }
 static inline void add(node_id i, i64 &x, i64 &p, PiecewiseLinearConvexfunction &f) {
  if (!i) return;
  push(i);
  add(ns[i].ch[0], x, p, f);
  f.add_ax_bx_c(0, ns[i].slope - p, x);
  x+= ns[i].dx, p= ns[i].slope;
  add(ns[i].ch[1], x, p, f);
 }
 node_id root;
 i64 lb;
 i128 lby;
public:
 void debugoutput() { debugoutput(root, 0); }
 // f(x) := 0
 PiecewiseLinearConvexfunction(): root(ni++), lb(-INF * 2), lby(0) { ns[root].sz= 1, ns[root].x= ns[root].dx= INF * 4, ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; }
 // f(x) := 0 if x == 0 else ∞
 PiecewiseLinearConvexfunction(int a): root(ni++), lb(0), lby(0) { ns[root].sz= 1, ns[root].x= ns[root].dx= ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; }
 i64 lower_bound() { return lb; }
 i64 upper_bound() { return lb + ns[root].x; }
 // f(x) + c
 void add_const(i64 c) { lby+= c; }
 // f(x) + ax+c
 void add_linear(i64 a, i128 c= 0) { lby+= i128(a) * lb + c, propagate(root, a); }
 // f(x-a)
 void shift(i64 a) { lb+= a; }
 // f(x) + a * max{x-c, 0}
 void add_relu(i64 a, i64 c) {
  if (c <= lower_bound()) return add_linear(a, -i128(a) * c);
  if (upper_bound() <= c) return;
  c-= lb, x_search(root, c);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx;
  if (l == c) {
   node_id i= ns[root].ch[0];
   ns[root].ch[0]= 0;
   propagate(root, a);
   push(root);
   ns[root].ch[0]= i;
  } else if (r == c) {
   propagate(ns[root].ch[1], a);
  } else {
   node_id i= ni++;
   ns[i].ch[0]= ns[i].laz= 0;
   ns[i].slope= ns[root].slope;
   ns[i].dx= r - c;
   if ((ns[i].ch[1]= ns[root].ch[1])) ns[ns[i].ch[1]].par= i;
   pushup(i), propagate(i, a);
   ns[root].ch[1]= i, ns[i].par= root;
   ns[root].dx= c - l, pushup(root);
  }
 }
 // f(x) + a * min{x-c,0} + b * max{x-c,0}
 void add_ax_bx_c(i64 a, i64 b, i64 c) { add_linear(a, -i128(a) * c), add_relu(b - a, c); }
 // f(x) + a * |x-c|
 void add_abs(i64 a, i64 c) { add_ax_bx_c(-a, a, c); }
 // min_{y∈[0,a]}{f(x-y)}
 void chmin_sliding_window(i64 a) {
  slope_search(root, 0);
  if (ns[root].slope) {
   node_id i= ni++;
   bool c= ns[root].slope < 0;
   if ((ns[i].ch[c]= ns[root].ch[c])) ns[ns[i].ch[c]].par= i;
   ns[i].laz= ns[i].ch[!c]= ns[i].slope= 0, ns[i].dx= a;
   pushup(i);
   ns[root].ch[c]= i, ns[i].par= root;
  } else ns[root].dx+= a;
  pushup(root);
 }
 // min_{y∈[a,b]}{f(x-y)}
 void chmin_sliding_window(i64 a, i64 b) { shift(a), chmin_sliding_window(b - a); }
 // min_{y∈[a,b]}{f(x-y) + cy}
 void convex_conv_range_linear(i64 a, i64 b, i64 c) { add_linear(-c), chmin_sliding_window(a, b), add_linear(c); }
 // ∞ if x<a else f(x)
 void chinfty_left(i64 a= 0) {
  if (a <= lower_bound()) return;
  assert(a < upper_bound());
  x_search(root, a - lb);
  i64 r= ns[root].dx;
  if (int i= ns[root].ch[0]; i) lby+= ns[i].y + i128(a - lb - ns[i].x) * ns[root].slope, r+= ns[i].x;
  else lby+= i128(a - lb) * ns[root].slope;
  if (r == a - lb) {
   root= ns[root].ch[1], ns[root].par= 0;
  } else {
   ns[root].dx= r - a + lb;
   ns[root].ch[0]= 0;
   pushup(root);
  }
  lb= a;
 }
 // ∞ if x>a else f(x)
 void chinfty_right(i64 a= 0) {
  if (upper_bound() <= a) return;
  assert(lower_bound() < a);
  x_search(root, a - lb);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0;
  if (l == a - lb) {
   root= ns[root].ch[0], ns[root].par= 0;
  } else {
   ns[root].dx= a - lb - l;
   ns[root].ch[1]= 0;
   pushup(root);
  }
 }
 // min_{y<=x} f(y)
 void cumulative_chmin() {
  slope_search(root, 0);
  if (ns[root].slope < 0) {
   if (!ns[root].ch[1]) ns[root].ch[1]= ni++;
   node_id i= ns[root].ch[1];
   ns[i].sz= 1, ns[i].x= ns[i].dx= INF * 2, ns[i].slope= ns[i].ch[0]= ns[i].ch[1]= ns[i].laz= ns[i].y= 0, ns[i].par= root;
  } else ns[root].ch[1]= 0, ns[root].dx= INF * 2, ns[root].slope= 0;
  pushup(root);
 }
 // min_{y>=x} f(y)
 void cumulative_chmin_rev() {
  slope_search(root, 0);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx, x= ns[root].slope > 0 ? l : r;
  if (int i= ns[root].ch[0]; i) lby+= ns[i].y + i128(x - ns[i].x) * ns[root].slope;
  else lby+= i128(x) * ns[root].slope;
  if (ns[root].slope > 0) {
   if (!ns[root].ch[0]) ns[root].ch[0]= ni++, lb= lb - INF * 2;
   lb+= l - INF * 2;
   node_id i= ns[root].ch[0];
   ns[i].sz= 1, ns[i].x= ns[i].dx= INF * 2, ns[i].slope= ns[i].ch[0]= ns[i].ch[1]= ns[i].laz= ns[i].y= 0, ns[i].par= root;
  } else ns[root].ch[0]= 0, ns[root].dx= INF * 2, ns[root].slope= 0, lb+= r - INF * 2;
  pushup(root);
 }
 i128 eval(i64 x) {
  if (x-= lb; x < 0 || ns[root].x < x) return INF;
  x_search(root, x);
  if (int i= ns[root].ch[0]; i) return lby + ns[i].y + i128(x - ns[i].x) * ns[root].slope;
  return lby + i128(x) * ns[root].slope;
 }
 std::array<i64, 2> argmin() {
  slope_search(root, 0);
  i64 l= lb + (ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0), r= l + ns[root].dx;
  if (ns[root].slope == 0) return {l, r};
  return ns[root].slope < 0 ? std::array{r, r} : std::array{l, l};
 }
 i128 min() { return eval(argmin()[0]); }
 int size() { return ns[root].sz; }
 // destructive
 PiecewiseLinearConvexfunction operator+(PiecewiseLinearConvexfunction &r) {
  if (size() > r.size()) std::swap(*this, r);
  r.chinfty_left(lower_bound()), r.chinfty_right(upper_bound());
  long long x= lower_bound(), p= 0;
  add(root, x, p, r), r.add_const(lby);
  return r;
 }
 // destructive
 PiecewiseLinearConvexfunction &operator+=(PiecewiseLinearConvexfunction &r) { return *this= *this + r; }
};
using namespace std;
// https://atcoder.jp/contests/abc127/tasks/abc127_f
namespace ABC127F {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int Q;
 cin >> Q;
 PiecewiseLinearConvexfunction f;
 while (Q--) {
  // debug(Q);
  int op;
  cin >> op;
  if (op == 1) {
   int a, b;
   cin >> a >> b;
   f.add_abs(1, a);
   f.add_const(b);
  } else {
   cout << f.argmin()[0] << " " << f.min() << '\n';
  }
  // f.debugoutput();
 }
 // f.debugoutput();
 // debug(f.lb);
 // debug(f.lby);
 return 0;
}
}
// https://atcoder.jp/contests/kupc2016/tasks/kupc2016_h
namespace atcoder_kupc2016_h {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long A[N], B[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 for (int i= 0; i < N; ++i) cin >> B[i];
 PiecewiseLinearConvexfunction f(1);
 for (int i= 0; i < N; ++i) {
  f.cumulative_chmin();
  f.shift(B[i] - A[i]);
  f.add_abs(1, 0);
 }
 cout << f.eval(0) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1467
namespace yukicoder1467 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using PLCF= PiecewiseLinearConvexfunction<>;
 int M, N;
 cin >> M >> N;
 long long A[M], B[N];
 for (int i= 0; i < M; ++i) cin >> A[i];
 for (int j= 0; j < N; ++j) cin >> B[j];
 vector<long long> vec(A, A + M);
 for (int j= 0; j < N; ++j) vec.push_back(B[j]);
 auto id= compress(vec);
 int n= vec.size();
 vector<long long> a(n), b(n);
 for (int i= 0; i < M; ++i) ++a[id(A[i])];
 for (int j= 0; j < N; ++j) ++b[id(B[j])];
 for (int k= 1; k <= M; ++k) {
  PLCF f(1);
  for (int i= 0; i < n; ++i) {
   f.cumulative_chmin();
   f.shift(a[i] - b[i] * k);
   if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0);
  }
  cout << f.eval(0) << '\n';
  PLCF::clear();
 }
 return 0;
}
}
// https://atcoder.jp/contests/arc070/tasks/arc070_c
namespace ARC070E {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f;
 long long pw;
 for (int i= 0; i < N; ++i) {
  long long l, r;
  cin >> l >> r;
  long long w= r - l;
  if (i) f.chmin_sliding_window(-w, pw);
  f.add_abs(1, l);
  pw= w;
 }
 cout << f.min() << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/abc217/tasks/abc217_h
namespace ABC217H {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f(1);
 long long pT= 0;
 for (int i= 0; i < N; ++i) {
  long long i64, D, X;
  cin >> i64 >> D >> X;
  long long dT= i64 - pT;
  f.chmin_sliding_window(-dT, dT);
  if (D) f.add_ax_bx_c(0, 1, X);
  else f.add_ax_bx_c(-1, 0, X);
  pT= i64;
 }
 cout << f.min() << '\n';
 return 0;
}
}
// https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Regional/2865
namespace AOJ2865 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long d[N - 1], g[N];
 for (int i= 0; i < N - 1; ++i) cin >> d[i];
 for (int i= 0; i < N; ++i) cin >> g[i];
 PiecewiseLinearConvexfunction f(1);
 for (int i= 0; i < N; ++i) {
  if (i) f.add_abs(d[i - 1], 0);
  f.add_const(g[i]);
  f.convex_conv_range_linear(-1, 1, g[i]);
 }
 cout << f.eval(0) << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/abc250/tasks/abc250_g
namespace ABC250G {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f(1);
 for (int i= 0; i < N; ++i) {
  int P;
  cin >> P;
  f.convex_conv_range_linear(-1, 1, P);
  f.chinfty_left();
 }
 cout << -f.min() << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/abc250/tasks/abc250_g
namespace ABC250G_Conj {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f;
 for (int i= 0; i < N; ++i) {
  int P;
  cin >> P;
  f.add_ax_bx_c(-1, 1, P);
  f.cumulative_chmin_rev();
 }
 cout << f.eval(0) << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/utpc2012/tasks/utpc2012_12
namespace atcoder_utpc2012_12 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, C;
 cin >> N >> C;
 vector<vector<int>> tree(N);
 vector<PiecewiseLinearConvexfunction<>> dp(N);
 dp[0].add_abs(1, C);
 for (int i= 1, P; i < N; i++) cin >> P >> C, tree[--P].push_back(i), dp[i].add_abs(1, C);
 auto dfs= [&tree, &dp](auto f, int v) -> void {
  for (int u: tree[v]) {
   f(f, u);
   dp[u].cumulative_chmin(), dp[u].shift(1);
   dp[v]+= dp[u];
  }
 };
 dfs(dfs, 0);
 cout << dp[0].min() << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/2114
namespace yukicoder2114 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using PLCF= PiecewiseLinearConvexfunction<>;
 int N, M, K;
 cin >> N >> M >> K;
 unordered_map<int, array<vector<int>, 2>> mp;
 for (int i= 0; i < N; ++i) {
  int B;
  cin >> B;
  mp[B % K][N > M].push_back(B / K);
 }
 for (int i= 0; i < M; ++i) {
  int R;
  cin >> R;
  mp[R % K][N < M].push_back(R / K);
 }
 long long ans= 0;
 for (auto &&[_, arr]: mp) {
  auto &&[A, B]= arr;
  if (A.size() > B.size()) {
   cout << -1 << '\n';
   return 0;
  }
  vector<int> vec(A);
  for (int i: B) vec.push_back(i);
  auto id= compress(vec);
  int n= vec.size();
  vector<int> a(n), b(n);
  for (int i: A) ++a[id(i)];
  for (int i: B) ++b[id(i)];
  PLCF f(1);
  for (int i= 0; i < n; ++i) {
   f.cumulative_chmin();
   f.shift(a[i] - b[i]);
   if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0);
  }
  ans+= f.eval(0);
  PLCF::clear();
 }
 cout << ans << '\n';
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC127F::main();
 // atcoder_kupc2016_h::main();
 // yukicoder1467::main();
 // ARC070E::main();
 // ABC217H::main();
 // ABC217H::main();
 // AOJ2865::main();
 // ABC250G::main();
 // ABC250G_Conj::main();
 // atcoder_utpc2012_12::main();
 yukicoder2114::main();
 return 0;
}