/* created by krps 本体は590行目あたりのsolve()に書いてあります。 Good Luck! */ import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.util.AbstractMap; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.NoSuchElementException; import java.util.PriorityQueue; import java.util.Queue; public class Main implements Runnable { public static void main(String[] args) { new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); //16MBスタックを確保して実行 } public void run() { for(int i=0;i<1;i++) { solver(); out.flush(); } } static FastScanner sc = new FastScanner(); static PrintWriter out = new PrintWriter(System.out); public static class Pair extends AbstractMap.SimpleEntry implements Comparable> { public Pair(final K key, final V value) { super(key, value); } @Override public int compareTo(Pair o) { Comparable key = (Comparable)this.getKey(); Comparable key2 = (Comparable)o.getKey(); /*if (false) { Comparable key3 = (Comparable) this.getValue(); Comparable key4 = (Comparable) o.getValue(); if (key.compareTo(key2) == 0) { return key3.compareTo(key4); } }*/ return key.compareTo(key2); } } private static boolean isPrime(long t) { if(t<2)return false; for(int i=2;i*i<=t;i++) { if(t%i==0)return false; } return true; } @SuppressWarnings("unused") private static long ncr(long n,long r) { long res=1; for(int i=0;i=0) { //p(t); res++; t=T.indexOf(v,t)+1; } return res; } private static int arrayMin(int a[]) { int res=INF; for(int i=0;i void p(T t) {out.println(t);} private static void p() {out.println();} private static void p(graph.edge2[] e) { for (int i = 0; i < e.length; i++) { out.println(e[i].to+" "+e[i].cost); } } private static void doubleToString(double a) { System.out.println(BigDecimal.valueOf(a).toPlainString()); } private static ArrayList> c; private static int[] ArrayListToList(ArrayList c2,int[] v) {for(int i=0;i ListToArrayList(int[] v) {ArrayList c=new ArrayList<>(v.length);for(int i=0;i0) { k=(k-1)/2; //System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2])); dat[k]=Cal(dat[k*2+1],dat[k*2+2]); } } //外から呼び出すときはl=0,r=-1,k=0にする。 void update(int a,int b,int k,int X,int l,int r) { if(r==-1)r=n; if(r<=a||b<=l) { return; } if(a<=l&&r<=b) { dat[k]=min(dat[k],X); }else { update(a, b, k*2+1,X, l, (l+r)/2); update(a, b,k*2+2,X,(l+r)/2,r); } } long get(int k) {//k番目の値を取得 0<=k x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1 return a - 1; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn return vr; } else { // 左の部分木を見て値をreturn return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); } } } int find_leftest_sub(int a, int b, long x, int k, int l, int r) { if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b return b; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); if (vl != b) { // 左の部分木を見て b 以外ならreturn return vl; } else { // 右の部分木を見て値をreturn return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); } } } //RSQ上で動きます。 int query2(long X) { int k=0; //ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい while(k*2+1=X) { k=k*2+1; }else { X-=dat[k*2+1]; k=k*2+2; } } return k-=n-1; } long Cal(long a,long b) { //計算アルゴリズム return (a+b); //return a|b; //return max(a,b); //return gcd(a, b); //return a^b; //return Math.min(a, b); } int size() { //Nではないよ、配列の大きさを返す。 return n; } //確認事項:Calとidentity //segmentTreeで宣言、initで初期化する。 void toString(int n) { for(int i=0;i=0;i--)node[i]=cal(node[i*2+1],node[i*2+2]); } void eval(int k,int l,int r) { //k番目のノードについて、遅延評価を行う? // 遅延配列が空でない場合、自ノード及び子ノードへの // 値の伝播が起こる if(lazy[k]!=identity) { node[k]+=lazy[k]; System.out.println(r); if(r-1>1) {//最下段かどうか lazy[2*k+1]=cal(lazy[k]/2, lazy[2*k+1]);//ここもRSQ以外未定義 /2するところを要変更 lazy[2*k+2]=cal(lazy[k]/2, lazy[2*k+1]); // 子ノードは親ノードの 1/2 の範囲であるため、 // 伝播させるときは半分にする } lazy[k]=identity; } } //区間加算,外から呼び出すときは、l=0,r=-1 void add(int a,int b,long x,int k,int l,int r) { //[a,b)の区間にxを加算する。 if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; if(a<=l&&r<=b) { lazy[k]=cal((r-1)*x,lazy[k]);//ここもRSQ以外未定義 *xするところを要変更 eval(k, l, r); }else { add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); node[k]=cal(node[2*k+1],node[2*k+2]); } } //区間和取得,外から呼び出すときは、l=0,r=-1 long getsum(int a,int b,int k,int l,int r) { if(r<0)r=n; if(b<=l||r<=a)return 0; eval(k, l, r); if(a<=l&&r<=b)return node[k]; long vl=getsum(a, b, 2*k+1, l, (l+r)/2); long vr=getsum(a, b, 2*k+2, (l+r)/2, r); return cal(vl,vr); } } static class IntsegmentTree{ int n; int dat[]; int identity;//単位元 IntsegmentTree(int N,int identity) {//setTreeの要素の数,単位元 this.identity =identity; init(N); } void init2() { Arrays.fill(dat, 0); } void init(int n_) { this.n=1; while(n0) { k=(k-1)/2; //System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2])); dat[k]=Cal(dat[k*2+1],dat[k*2+2]); } } //外から呼び出すときはl=0,r=-1,k=0にする。 void update(int a,int b,int k,int X,int l,int r) { if(r==-1)r=n; if(r<=a||b<=l) { return; } if(a<=l&&r<=b) { dat[k]=min(dat[k],X); }else { update(a, b, k*2+1,X, l, (l+r)/2); update(a, b,k*2+2,X,(l+r)/2,r); } } int get(int k) {//k番目の値を取得 0<=k x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1 return a - 1; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn return vr; } else { // 左の部分木を見て値をreturn return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); } } } int find_leftest_sub(int a, int b, long x, int k, int l, int r) { if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b return b; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); if (vl != b) { // 左の部分木を見て b 以外ならreturn return vl; } else { // 右の部分木を見て値をreturn return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); } } } //RSQ上で動きます。 int query2(int X) { int k=0; //ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい while(k*2+1=X) { k=k*2+1; }else { X-=dat[k*2+1]; k=k*2+2; } } return k-=n-1; } int Cal(int a,int b) { //計算アルゴリズム return (a+b); //return a|b; //return max(a,b); //return gcd(a, b); //return a^b; //return Math.min(a, b); } int size() { //Nではないよ、配列の大きさを返す。 return n; } //確認事項:Calとidentity //segmentTreeで宣言、initで初期化する。 void toString(int n) { for(int i=0;i{ int y,z; int x,a,b,C; int count; int dep; String S; V(int x,int y){ this.x=x; this.y=y; } V(int a,int b,int C){ this.a=a; this.b=b; this.x=C; } public int compareTo(V o) { Comparable key = (Comparable)this.x; Comparable key2 = (Comparable)o.x; Comparable key3 = (Comparable)this.y; Comparable key4 = (Comparable)o.y; if(key.compareTo(key2)==0) { return key3.compareTo(key4); } return key.compareTo(key2); } } static long LINF =(1L<<63)-1,mod7=Pow(10,9)+7,mod9=Pow(10,9)+9,count=0,sum=0,max=-LINF,min=LINF,ans=0,temp; static int i=0,INF=(1<<31)-1,compmax=0; static long A[]; private static void solver() { int N = sc.nextInt(); int A[] = sc.nextIntArray(N); int B[] = sc.nextIntArray(N); long V=0; long T=0; for (int i = 0; i 2){ long c1=(max-min)/3+min; long c2=(max-min)*2/3+min; if(F(c1)>=F(c2)) { min=c1; }else{ max=c2; } } for(long i=min-1;i<=max+1;i++) { F(i); } } static long F(long V) { long res=0; //b0をVに固定する long b=V; long c=A[0]-b; res+=abs(b)+abs(c); for (int i = 1; i < A.length; i++) { if(A[i]>A[i-1]) { //増加した。 b=A[i]-c; }else if(A[i]d) { //完全に含まれない。 return (b-a+1)+(d-c+1); } if(c<=a&&b<=d) { //完全に含まれる1 return d-c+1; } if(a<=c&&d<=b) { //完全に含まれる2 return b-a+1; } //一部だけ含まれる。 if(c<=b&&b<=d) { //[c,b]が含まれる。 return d-a+1; } if(c<=a&&a<=d) { return b-c+1; } return -1; } static boolean check(int HW[][],int i,int t,int W) { while(t> m,int N) { int BACK[]=new int[N]; Arrays.fill(BACK, -1); for (int i = 0; i < N; i++) { if(BACK[i]!=-1)continue; getBackQuery(m, i, BACK); BACK[BACK_COUNT]=i; } Map> reversedm=new HashMap<>(); for(int Vex:m.keySet()) { for(int TO:m.get(Vex)) { if(!reversedm.containsKey(TO))reversedm.put(TO, new ArrayList<>()); reversedm.get(TO).add(Vex); } } uf=new unionFind(N); for (int i = N-1; i>=0;i--) { //iを始点として、DFSを行う。到達可能マスが同じグループ if(uf.get(i)!=i)continue; sccquery(reversedm, i); } } static void sccquery(Map> reversedm,int vex) { if(!reversedm.containsKey(vex)||reversedm.get(vex).size()==0)return; for(int TO:reversedm.get(vex)) { if(uf.find(vex)==uf.find(TO))continue; uf.union(vex, TO); sccquery(reversedm, vex); } } static int BACK_COUNT; static unionFind uf; static void getBackQuery(Map> m,int Vex,int BACK[]) { if(!m.containsKey(Vex)||m.get(Vex).size()==0)return; for(int TO:m.get(Vex)) { if(BACK[TO]!=-1)continue; BACK[TO]=-2; getBackQuery(m, Vex, BACK); BACK[BACK_COUNT++]=TO; } } static ArrayList Vs; static void getTopo(Map> m,int N) { boolean flag[]=new boolean[N]; Arrays.fill(flag, false); Vs=new ArrayList<>(); for(int V:m.keySet()) { if(flag[V])continue; flag[V]=true; topoQuery(m, V, flag); Vs.add(V); } Collections.reverse(Vs); } static void topoQuery(Map> m,int Vex, boolean flag[]) { //Vexからスタート //これ、閉路がある時に対応できてなくね if(!m.containsKey(Vex)||m.get(Vex).size()==0)return; for(int to:m.get(Vex)) { if(flag[to])continue; flag[to]=true; topoQuery(m, to,flag); Vs.add(to); } } static class Flow{ static class edge{ int to,cap,rev; public edge(int to,int cap,int rev) { // TODO 自動生成されたコンストラクター・スタブ this.to=to; this.cap=cap; this.rev=rev; } } public Flow(int N) { // TODO 自動生成されたコンストラクター・スタブ this.N=N;//頂点数 init(); } void init() { used=new boolean[N]; G=new ArrayList<>(); for (int i = 0; i < N; i++) { G.add(new ArrayList<>()); } } int N; ArrayList> G;//iがfromを意味する 隣接リスト表現 boolean used[]; //from->toへ向かう容量capの辺をグラフに追加する。 void add_edge(int from,int to,int cap) { G.get(from).add(new edge(to, cap, G.get(to).size())); G.get(to).add(new edge(from, 0, G.get(from).size()-1)); } //最大流を求める 最悪計算量はO(F|E|) Fは流量,Eは辺の数? int max_flow(int s,int t) { int flow=0; while(true) { Arrays.fill(used, false); int f=dfs(s,t,INF); if(f==0)return flow; flow+=f; } } int dfs(int v,int t,int f) { if(v==t)return f;//tに到着したら終了 used[v]=true;//vに訪れたことを表す for (int i = 0; i < G.get(v).size(); i++) { edge e=G.get(v).get(i); if(used[e.to]||e.cap<=0)continue; int d=dfs(e.to, t, Math.min(f,e.cap)); if(d>0) { e.cap-=d; G.get(e.to).get(e.rev).cap+=d; return d; } } return 0; } //デバッグ用 void get_edges(int T) { //頂点Tから出る辺を出力する int cout=0; for(edge e:G.get(T)) { System.out.println(cout+++" "+T+"=>"+e.to+" "+e.cap); } } } static class LCA{ int N;//頂点の数(頂点名は、0-indexで命名) int dist[];//rootから頂点iまでの距離 int root;//木の根 int parents[];//頂点iの親がparents[i] int doubling[][]; public LCA(Map> m,int N,int root) { //一般グラフを受け取って、そこから木を生成する。 this.root=root; init(m,N); } void init(Map> m,int N) { this.N=N; parents=new int[N]; dist=new int[N]; doubling=new int[31][N]; dfs(m); init_doubling(); } void dfs(Map> m) { //根からの距離と親を求める。 boolean flag[]=new boolean[N]; Arrays.fill(flag, false); flag[root]=true; parents[root]=root; Queue qq = new ArrayDeque<>(); //始点を保存 qq.add(root); while(!qq.isEmpty()) { int VEX=qq.poll(); if(!m.containsKey(VEX)||m.get(VEX).size()==0)continue; for(int TO:m.get(VEX)) { if(flag[TO])continue; flag[TO]=true; parents[TO]=VEX; dist[TO]=dist[VEX]+1; qq.add(TO); } } } void init_doubling() { //ダブリングによって、2^k先の祖先を前計算する。 //doubling[T][i]=iから2^T個分先 for (int i = 0; i < N; i++) { doubling[0][i]=parents[i]; } for (int T = 1; T < doubling.length; T++) { for (int i = 0; i < N; i++) { doubling[T][i]=doubling[T-1][doubling[T-1][i]]; } } } int get_doubling(int from,int K) { //ダブリングによって、fromからK先の祖先を求める。 //longにするときは、doublingの長さも変えないとだから注意 int res=from; for (int i = 0; i < doubling.length; i++) { if(((K>>i)&1)==0)continue; res=doubling[i][res]; } return res; } int query(int u1,int v1) { //親からの距離を等しくする。(dist[u1]>dist[v1]とする) //System.out.println(u1+" "+v1+" "+get_doubling(u1, dist[u1]-dist[v1])); u1=get_doubling(u1, dist[u1]-dist[v1]); if(u1==v1)return v1; //二分探索によって、LCAの手前まで移動させる。 int G=30; while(G>=0) { int uTO=doubling[G][u1]; int vTO=doubling[G][v1]; if(uTO!=vTO) { u1=uTO; v1=vTO; } G--; } //System.out.println(parents[u1]+" "+parents[v1]+" "+dist[u1]+" "+dist[v1]+" "+u1+" "+v1); return parents[u1]; } int get_LCA(int u,int v) { //根をrootとした時の、u,vのLCAを返す。(0-indexed) if(dist[u]dist[v]とする。 return query(u,v); } int get_dist(int u,int v) { //u-vの距離 return dist[u]+dist[v]-2*dist[get_LCA(u, v)]; } boolean is_on_path(int u,int v,int a) { //u-vパス上に頂点aがあるか? //true:ある //false:ない return get_dist(u, a)+get_dist(a, v)==get_dist(u, v); } } static class doubling{ int N; int bits; int doubling[][]; long COST[][]; public doubling(int A[],int bits) { this.bits=bits; this.N=A.length; init1(A); } public doubling(int A[],int bits,long C[]) { // TODO 自動生成されたコンストラクター・スタブ //long C[]は、i=>A[i]に行くコスト //query2は、iからK番先までのコストの和で、i番までのコストが足されないので注意 this.bits=bits; this.N=A.length; init1(A); init2(C); } private void init1(int A[]) { // TODO 自動生成されたメソッド・スタブ doubling=new int[bits][N]; for (int i = 0; i < N; i++) { doubling[0][i]=A[i]; } for (int t = 0; t+1 < bits; t++) { for (int i = 0; i < N; i++) { doubling[t+1][i]=doubling[t][doubling[t][i]]; } } } private void init2(long C[]) { COST=new long[bits][N]; for (int i = 0; i < N; i++) { COST[0][i]=C[i];//i番目からA[i]までのコスト } for (int t = 0; t+1 < bits; t++) { for (int i = 0; i < N; i++) { COST[t+1][i]=COST[t][doubling[t][i]]+COST[t][i]; } } } //解釈 private int query1(int start,long K) { //startからK回移動した後の座標を求める。 int now=start; for (int i = 0; i < bits; i++) { if(((K>>i)&1)==1)now=doubling[i][now]; } return now; } private long query2(int start,long K,long mod) { //STARTからK回移動した時のコストを計算する。 int now=start; long res=0; for (int i = 0; i < bits; i++) { if(((K>>i)&1)==1) { res+=COST[i][now]; now=doubling[i][now]; res%=mod; } } return res; } private int query3(int start) { //startからスタートして、ループに入る時、そのループの長さを返す。 return 1; } } static class DIKSTR{ ArrayList> m; static Map hash=new HashMap<>(); static int hash_count=0; long d[]; int V,E; class edge2{ int to; long cost; public edge2(int to,long cost) { this.to=to; this.cost=cost; } } class pair implements Comparable{ int VEX; long cost; public pair(long cost,int VEX) { this.VEX=VEX; this.cost=cost; } public int compareTo(pair o) { Comparable key = (Comparable)this.cost; Comparable key2 = (Comparable)o.cost; return key.compareTo(key2); } } public DIKSTR(int V,int E) { this.V=V;//最大の頂点数。 this.E=E;//最大の辺数。 init(); } public DIKSTR(int V) { this.V=V; this.E=0; init(); } void init() { m=new ArrayList<>(); for (int i = 0; i < V; i++) { m.add(new ArrayList<>()); } d=new long[V]; } void add_edge(int FROM,int TO,long COST) { m.get(FROM).add(new edge2(TO, COST)); } void add_edge(String FROM,String TO,long COST) { if(!hash.containsKey(FROM))hash.put(FROM, hash_count++); if(!hash.containsKey(TO))hash.put(TO, hash_count++); add_edge(get_hash(FROM), get_hash(TO), COST); } int get_hash(String T) { if(!hash.containsKey(T)) { hash.put(T, hash_count++); } return hash.get(T); } long[] dikstr(String r) { return dikstr(get_hash(r)); } long[] dikstr(int r) {//rは始点 Arrays.fill(d, LINF); d[r]=0; PriorityQueue p = new PriorityQueue<>();//add poll p.add(new pair(0L, r)); while(!p.isEmpty()) { pair x=p.poll(); int from=x.VEX; if(x.cost>d[from])continue; for (int i = 0; i < m.get(from).size(); i++) { edge2 e=m.get(from).get(i); long COST=COST(e.cost); if(d[e.to]>d[from]+COST) { d[e.to]=d[from]+COST; p.add(new pair(d[e.to], e.to)); } } } return d.clone(); } long COST(long e_cost) { return e_cost; } } static Map> getTree(int N){ Map> m = new HashMap<>(); for (int i = 0; i < N; i++) { int a = sc.nextInt() - 1, b = sc.nextInt() - 1; if (!m.containsKey(a)) m.put(a, new ArrayList()); if (!m.containsKey(b)) m.put(b, new ArrayList()); m.get(a).add(b); m.get(b).add(a); } return m; } static Map> makeTree(Map> m){ //頂点0を根とした木を構築する。 Queue qq = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される Queue parent = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される qq.add(0); Map> T = new HashMap<>(); parent.add(-1); while (!qq.isEmpty()) { int i = qq.poll(); int p = parent.poll(); if (!T.containsKey(i)) T.put(i, new ArrayList()); for (int V : m.get(i)) { if (V == p) continue; qq.add(V); parent.add(i); T.get(i).add(V); } } return T; } static boolean isHaveSameBit(int a,int b) {//同じbitを持っているか int t=0; while((a>>t)!=0) { if(((a>>t)&1)==1&&((b>>t)&1)==1)return true; t++; } return false; } static boolean isPalindrome(String S) {//回分になってるか for (int i = 0; i < S.length()/2; i++) { if(S.charAt(i)!=S.charAt(S.length()-i-1)) { return false; } } return true; } static long modinv(long a,long mod) { long b=mod,u=1,v=0; while(b!=0) { long t=a/b; a-=t*b;long tem=a;a=b;b=tem; u-=t*v;tem=u;u=v;v=tem; } u%=mod; if(u<0)u+=mod; return u; } static long[] extendedGCD(long a, long b) { long s = 0, old_s = 1; long t = 1, old_t = 0; long r = b, old_r = a; while(r != 0) { long q = old_r / r; long old_s0 = old_s, old_t0 = old_t, old_r0 = old_r; old_s = s; s = old_s0 - q * s; old_t = t; t = old_t0 - q * t; old_r = r; r = old_r0 - q * r; } return new long[] {old_s, old_t}; } static class graph{ public graph() { // TODO 自動生成されたコンストラクター・スタブ } //コンテスト中だけ static class edge3{ int to; long cost; int K; public edge3(int to,long cost) { this.to=to; this.cost=cost; } public edge3(int to,long cost,int K) { this.to=to; this.cost=cost; this.K=K; } } long costV(long T,int K) { //T以上の最小のKの倍数を返す。 long V=(T+K-1)/K; return V*K; } long[] adddikstr(int V,int E,int r,Map> m) { d=new long[V]; Arrays.fill(d, LINF); d[r]=0; PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0L, r)); while(!p.isEmpty()) { Pair x=p.poll(); int from=x.getValue(); if(x.getKey()>d[from])continue; if(!m.containsKey(from))continue; for (int i = 0; i < m.get(from).size(); i++) { edge3 e=m.get(from).get(i); if(d[e.to]>costV(d[from],e.K)+e.cost) { d[e.to]=costV(d[from],e.K)+e.cost; p.add(new Pair(d[e.to], e.to)); } } } return d; } // class edge implements Comparable{ int from,to,cost; public edge(int from,int to,int cost) { this.from=from; this.to=to; this.cost=cost; } @Override public int compareTo(edge o) { Comparable key = (Comparable)this.cost; Comparable key2 = (Comparable)o.cost; return key.compareTo(key2); } } static class edge2{ int to; long cost; String FROM,TO; public edge2(int to,long cost) { this.to=to; this.cost=cost; } public edge2(int to,long cost,String FROM,String TO) { this.to=to; this.cost=cost; this.FROM=FROM; this.TO=TO; } } //単一始点最短距離問題(ダイクストラ法) 負閉路対策不可 経路復元 long d[]; long[] dikstr(int V,int E,int r,Map> m) { //int path[]=new int[V]; //Arrays.fill(path, -1); d=new long[V]; Arrays.fill(d, LINF); d[r]=0; PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0L, r)); while(!p.isEmpty()) { Pair x=p.poll(); int from=x.getValue(); if(x.getKey()>d[from])continue; if(!m.containsKey(from))continue; for (int i = 0; i < m.get(from).size(); i++) { edge2 e=m.get(from).get(i); if(d[e.to]>d[from]+e.cost) { d[e.to]=d[from]+e.cost; p.add(new Pair(d[e.to], e.to)); //path[e.to]=from; } } } //経路復元 //複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく //ArrayList PATHs = new ArrayList<>(); //int t=V-1;//goalから逆算する この場合0=goal //for(;t!=-1;t=path[t]) { // PATHs.add(t); //} //p(path); //Collections.reverse(PATHs); //System.out.println(PATHs); return d.clone(); } long[] additionalDikstr(int V,int E,int r,Map> m,int banned) { //int path[]=new int[V]; //Arrays.fill(path, -1); d=new long[V]; Arrays.fill(d, LINF); d[r]=0; PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0L, r)); while(!p.isEmpty()) { Pair x=p.poll(); int from=x.getValue(); if(x.getKey()>d[from])continue; if(!m.containsKey(from))continue; for (int i = 0; i < m.get(from).size(); i++) { edge2 e=m.get(from).get(i); if(from==banned&&e.to==0)continue; if(d[e.to]>d[from]+e.cost) { d[e.to]=d[from]+e.cost; p.add(new Pair(d[e.to], e.to)); } } } return d.clone(); } int D[]; int[] Intdikstr(int V,int E,int r,Map> m) { //int path[]=new int[V]; //Arrays.fill(path, -1); D=new int[V]; Arrays.fill(D, INF); D[r]=0; PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0, r)); while(!p.isEmpty()) { Pair x=p.poll(); int from=x.getValue(); if(x.getKey()>D[from])continue; if(!m.containsKey(from))continue; for (int i = 0; i < m.get(from).size(); i++) { edge2 e=m.get(from).get(i); if(D[e.to]>D[from]+e.cost) { D[e.to]=(int) (D[from]+e.cost); p.add(new Pair(D[e.to], e.to)); //path[e.to]=from; } } } p.clear(); //経路復元 //複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく //ArrayList PATHs = new ArrayList<>(); //int t=V-1;//goalから逆算する この場合0=goal //for(;t!=-1;t=path[t]) { // PATHs.add(t); //} //p(path); //Collections.reverse(PATHs); //System.out.println(PATHs); return D; } //単一始点最短距離問題(ベルマンフォード法) 負閉路対策済み int[] Bellman_Ford(int V,int E,int r,edge e[]) { int d[]=new int[V]; //0~eのグラフはこれ //Map d = new HashMap<>();それ以外はこれ //for(int i=0;i(e[i].to, INF)); // if(!d.containsKey(e[i].from))m.add(new Pair(e[i].from, INF)); //} //d.replace(r, 0); Arrays.fill(d, INF); d[r]=0; int count=0; while(true) { boolean update =false; for(int i=0;i>1; } return res; } private static Map primeNumbers(long N) {//素因数列挙 Map c = new HashMap<>(); for(long i=2;i*i<=N;i++) { if(N%i==0) { int count=0; while(N%i==0) { N/=i; count++; } c.put(i, count); continue; } } if(N!=1) { c.put(N, 1); } return c; } //=========================Union Find============================================= //union idx2 tree to idx1 tree O(a(N)) static class unionFind{ int UNI[],n; public unionFind(int N) { // TODO 自動生成されたコンストラクター・スタブ n=N; init(); } void init() { UNI=new int[n]; for (int i = 0; i < n; i++) { UNI[i]=i; } } int get(int idx) { return UNI[idx]; } int find(int idx) {//木の根のindexを返す if(UNI[idx]==idx) return idx; return UNI[idx] = find(UNI[idx]); } void shape() {//木の根に直接つなげる 経路圧縮 for(int i=0;ic.get(root2).size()) { //root2をroot1に移し替える for(int a:c.get(root2).keySet()) { if(!c.get(root1).containsKey(a)) { c.get(root1).put(a, 0); } c.get(root1).replace(a, c.get(root1).get(a)+c.get(root2).get(a)); } tree[root2] = root1; }else { for(int a:c.get(root1).keySet()) { if(!c.get(root2).containsKey(a)) { c.get(root2).put(a, 0); } c.get(root2).replace(a, c.get(root2).get(a)+c.get(root1).get(a)); } tree[root1] = root2; } } } //=========================二分探索============================================= private static class binarySerch{ public binarySerch() { // TODO 自動生成されたコンストラクター・スタブ } int BinarySearch(int A[],int value) { int S=0,E=A.length,G=-1; while(S<=E) { G=(S+E)/2; if(A[G]==value)return G; else if(A[G]>value) { if(E==G)break;E=G; }else if(A[G]=value)return 0; if(A[A.length-1]=value&&A[G-1]=value) { E=G; }else if(A[G]value)return 0; if(A[A.length-1]<=value)return A.length; while(true) { G=(S+E)/2; if(A[G]>value&&A[G-1]<=value) { return G; }else if(A[G]>value) { E=G; }else if(A[G]<=value) { S=G; } } } int lowerBound(long A[],long value) { //A[i-1]=value)return 0; if(A[A.length-1]=value&&A[G-1]=value) { E=G; }else if(A[G]value)return 0; if(A[A.length-1]<=value)return A.length; while(true) { G=(S+E)/2; if(A[G]>value&&A[G-1]<=value) { return G; }else if(A[G]>value) { E=G; }else if(A[G]<=value) { S=G; } } } int lowerBound(ArrayList A,int value) { //A[i-1]=value)return 0; if(A.get(A.size()-1)=value&&A.get(G-1)=value) { E=G; }else if(A.get(G) A,int value) { //A[i-1]<=valuevalue)return 0; if(A.get(A.size()-1)<=value)return A.size(); while(true) { G=(S+E)/2; if(A.get(G)>value&&A.get(G-1)<=value) { return G; }else if(A.get(G)>value) { E=G; }else if(A.get(G)<=value) { S=G; } } } int lowerBound(ArrayList A,long value) { //A[i-1]=value)return 0; if(A.get(A.size()-1)=value&&A.get(G-1)=value) { E=G; }else if(A.get(G) A,long value) { //A[i-1]<=valuevalue)return 0; if(A.get(A.size()-1)<=value)return A.size(); while(true) { G=(S+E)/2; if(A.get(G)>value&&A.get(G-1)<=value) { return G; }else if(A.get(G)>value) { E=G; }else if(A.get(G)<=value) { S=G; } } } } private static long modNcR2(int n,int r,int mod) { if(r<0||n>1; } return res; } private static long min(long ...a) { long m=a[0]; for(int i=0;i=0;x--) { if(dp[x])dp[x+a[i]]=true; } } p(dp[K] ? "Yes":"No"); } static String nextPermutation(String s) { ArrayList list=new ArrayList(); for(int i=0;i=0;i--) { if(list.get(i)=L;i--) { if(pivot