import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } // Update g by g[i] := min{ g[i], min{ g[j] + f(j, i) | 0 <= j < i } } // i -> argmin{ g[j] + f(j, i) | 0 <= j < i } is increasing void monotoneDP(T)(T[] g, in T delegate(int, int) f) { void update(int jL, int jR, int iL, int iR) { if (iL == iR) return; const iMid = (iL + iR) / 2; T opt = g[jL] + f(jL, iMid); int jOpt = jL; foreach (j; jL + 1 .. jR) if (chmin(opt, g[j] + f(j, iMid))) jOpt = j; chmin(g[iMid], opt); update(jL, jOpt + 1, iL, iMid); update(jOpt, jR, iMid + 1, iR); } void solve(int l, int r) { if (l + 1 == r) return; const mid = (l + r) / 2; solve(l, mid); update(l, mid, mid, r); solve(mid, r); } solve(0, cast(int)(g.length)); } enum INF = 10L^^18; int N; long[] A, X, Y; void main() { try { for (; ; ) { N = readInt(); A = new long[N]; foreach (i; 0 .. N) { A[i] = readLong(); } X = new long[N]; foreach (i; 0 .. N) { X[i] = readLong(); } Y = new long[N]; foreach (i; 0 .. N) { Y[i] = readLong(); } debug { auto dpBrute = new long[N + 1]; dpBrute[] = INF; dpBrute[0] = 0; foreach (i; 1 .. N + 1) { foreach (j; 0 .. i) { chmin(dpBrute[i], dpBrute[j] + (X[j] - A[i - 1])^^2 + (Y[j] - 0)^^2); } } writeln(dpBrute); } auto dp = new long[N + 1]; dp[] = INF; dp[0] = 0; dp.monotoneDP((j, i) => (X[j] - A[i - 1])^^2 + (Y[j] - 0)^^2); debug { writeln(dp); } writeln(dp[N]); } } catch (EOFException e) { } }