結果

問題 No.200 カードファイト!
ユーザー バイトバイト
提出日時 2018-08-16 23:07:14
言語 Java19
(openjdk 21)
結果
WA  
実行時間 -
コード長 27,307 bytes
コンパイル時間 3,797 ms
コンパイル使用メモリ 95,884 KB
実行使用メモリ 115,692 KB
最終ジャッジ日時 2023-07-27 20:12:40
合計ジャッジ時間 8,425 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

package com.company;

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

/**
 * @author baito
 */
class P implements Comparable<P>
{
    int x, y;

    P(int a, int b)
    {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object o)
    {
        if (this == o) return true;
        if (!(o instanceof P)) return false;
        P p = (P) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode()
    {
        return Objects.hash(x, y);
    }

    @Override
    public int compareTo(P p)
    {
        return x == p.x ? y - p.y : x - p.x; //xで昇順にソート
        //return (x == p.x ? y - p.y : x - p.x) * -1; //xで降順にソート
        //return y == p.y ? x - p.x : y - p.y;//yで昇順にソート
        //return (y == p.y ? x - p.x : y - p.y)*-1;//yで降順にソート
    }
}

@SuppressWarnings("unchecked")
public class Main
{
    static StringBuilder sb = new StringBuilder();
    static int INF = 1234567890;
    static int MINF = -1234567890;
    static long LINF = 123456789123456789L;
    static long MLINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y4 = {0, 1, 0, -1};
    static int[] x4 = {1, 0, -1, 0};
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] Fa;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;
    static long maxRes = MLINF;
    static long minRes = LINF;

    static int N, a, b;
    static int ac[], bc[];

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        a = ni();
        ac = nia(a);
        b = ni();
        bc = nia(b);
        long startTime = System.currentTimeMillis();
        PrimalDual pri = new PrimalDual(a + b + 2);
        int s = a + b;
        int t = a + b + 1;
        for (int i = 0; i < a; i++)
        {
            pri.addEdge(s, i, 1, 0);
        }
        for (int i = 0; i < b; i++)
        {
            pri.addEdge(i + a, t, 1, 0);
        }

        for (int f = 0; f < a; f++)
        {
            for (int to = 0; to < b; to++)
            {
                if (ac[f] <= bc[to]) pri.addEdge(f, to + a, LINF, 1);
                else pri.addEdge(f, to + a, LINF, 0);
            }
        }
        System.out.println(N - pri.solve(s, t, N));

        long endTime = System.currentTimeMillis();
        System.err.println(endTime - startTime);
    }

    static class PrimalDual//最小費用流
    {
        static ArrayList<Edge>[] edges;
        static int s, t;

        PrimalDual(int n)
        {
            edges = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new);
        }

        public static void addEdge(int f, int t, long ca, long co)
        {
            edges[f].add(new Edge(t, ca, co, edges[t].size()));
            edges[t].add(new Edge(f, 0, -co, edges[f].size() - 1));
        }

        static class Dist implements Comparable<Dist>
        {
            int v;
            long dist;

            Dist(long a, int b)
            {
                dist = a;
                v = b;
            }

            @Override
            public boolean equals(Object o)
            {
                if (this == o) return true;
                if (!(o instanceof Dist)) return false;
                Dist d = (Dist) o;
                return dist == d.dist && v == d.v;
            }

            @Override
            public int hashCode()
            {
                return Objects.hash(dist, v);
            }

            @Override
            public int compareTo(Dist d)
            {
                return dist > d.dist ? 1 : -1; //xで昇順にソート
                //return (dist == d.dist ? v - d.v : dist - d.dist) * -1; //xで降順にソート
                //return v == d.v ? dist - d.dist : v - d.v;//yで昇順にソート
                //return (v == d.v ? dist - d.dist : v - d.v)*-1;//yで降順にソート
            }
        }

        public static void update(long usedf)
        {
            int a = Main.a;
            int b = Main.b;
            if (usedf % b == 0)
            {
                //ゴールへの量を1にする
                for (int bi = a; bi < b + a; bi++)
                {
                    for (Edge e : edges[bi])
                    {
                        if (e.cap == 0) e.cap = 1;
                        else e.cap = 0;
                    }
                }
            }
            if (usedf % a == 0)
            {
                //スタートへの量を1にする
                for (Edge edge : edges[s])
                {
                    edge.cap = 1;
                }
            }
        }

        //最小の費用流
        static long solve(int s, int t, long f)
        {
            PrimalDual.s = s;
            PrimalDual.t = t;
            int V = edges.length;
            int[] prevv = new int[V];
            int[] preve = new int[V];
            long[] dist = new long[V];
            long[] h = new long[V];
            long res = 0;
            long F = f;
            while (f > 0)
            {
                Arrays.fill(dist, LINF);
                dist[s] = 0;
                PriorityQueue<Dist> que = new PriorityQueue<>();
                que.add(new Dist(0, s));
                while (!que.isEmpty())
                {
                    Dist d = que.poll();
                    int v = d.v;
                    if (dist[v] < d.dist) continue;
                    for (int i = 0; i < edges[v].size(); i++)
                    {
                        Edge e = edges[v].get(i);
                        long ndis = d.dist + e.cost + h[v] - h[e.to];
                        if (e.cap > 0 && dist[e.to] > ndis && ndis >= 0)
                        {
                            dist[e.to] = ndis;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            que.add(new Dist(dist[e.to], e.to));
                        }
                    }
                }
                if (dist[t] >= INF)
                {
                    update(F - f);
                    Arrays.fill(h, 0);
                    continue;
                }
                for (int i = 0; i < V; i++) h[i] += dist[i];
                long d = f;
                for (int v = t; v != s; v = prevv[v])
                {
                    d = Math.min(d, edges[prevv[v]].get(preve[v]).cap);
                }
                f -= d;
                res += d * h[t];
                for (int v = t; v != s; v = prevv[v])
                {
                    Edge e = edges[prevv[v]].get(preve[v]);
                    e.cap -= d;
                    edges[v].get(e.rev).cap += d;
                }
            }
            return res;
        }

        static class Edge
        {
            int to, rev;
            long cap, cost;

            Edge(int t, long ca, long co, int r)
            {
                to = t;
                cap = ca;
                cost = co;
                rev = r;
            }
        }
    }


    public static void chMax(long v)
    {
        maxRes = Math.max(maxRes, v);
    }

    public static void chMin(long v)
    {
        minRes = Math.min(minRes, v);
    }

    public static boolean solve(long v)
    {
        return true;
    }

    //条件を満たす最大値、あるいは最小値を求める
    static long binarysearch(long ok, long ng)
    {
        //int ok = 0; //解が存在する
        //int ng = N; //解が存在しない
        while (Math.abs(ok - ng) > 1)
        {
            long mid;
            if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
            else mid = ok + (ng - ok) / 2;

            if (solve(mid))
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        return ok;
    }

    public static boolean bitGet(BitSet bit, int keta)
    {
        return bit.nextSetBit(keta) == keta;
    }

    public static boolean bitGet(long bit, int keta)
    {
        return ((bit >> keta) & 1) == 1;
    }

    public static int restoreHashA(long key)
    {
        return (int) (key >> 32);
    }

    public static int restoreHashB(long key)
    {
        return (int) (key & -1);
    }

    //正の数のみ
    public static long getHashKey(int a, int b)
    {
        return (long) a << 32 | b;
    }

    public static long sqrt(long v)
    {
        long res = (long) Math.sqrt(v);
        while (res * res > v) res--;
        return res;
    }

    public static int u0(int a)
    {
        if (a < 0) return 0;
        return a;
    }

    public static long u0(long a)
    {
        if (a < 0) return 0;
        return a;
    }

    public static Integer[] toIntegerArray(int[] ar)
    {
        Integer[] res = new Integer[ar.length];
        for (int i = 0; i < ar.length; i++)
        {
            res[i] = ar[i];
        }
        return res;
    }

    //k個の次の組み合わせをビットで返す 大きさに上限はない 110110 -> 111001
    public static int nextCombSizeK(int comb, int k)
    {
        int x = comb & -comb; //最下位の1
        int y = comb + x; //連続した下の1を繰り上がらせる
        return ((comb & ~y) / x >> 1) | y;
    }

    public static int keta(long num)
    {
        int res = 0;
        while (num > 0)
        {
            num /= 10;
            res++;
        }
        return res;
    }


    public static boolean isOutofIndex(int x, int y)
    {
        if (x < 0 || y < 0) return true;
        if (map[0].length <= x || map.length <= y) return true;
        return false;
    }

    public static void setPrimes()
    {
        int n = 100001;
        isPrime = new boolean[n];
        List<Integer> prs = new ArrayList<>();
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++)
        {
            if (!isPrime[i]) continue;
            prs.add(i);
            for (int j = i * 2; j < n; j += i)
            {
                isPrime[j] = false;
            }
        }
        primes = new int[prs.size()];
        for (int i = 0; i < prs.size(); i++)
            primes[i] = prs.get(i);
    }

    public static void revSort(int[] a)
    {
        Arrays.sort(a);
        reverse(a);
    }

    public static void revSort(long[] a)
    {
        Arrays.sort(a);
        reverse(a);
    }

    public static int[][] copy(int[][] ar)
    {
        int[][] nr = new int[ar.length][ar[0].length];
        for (int i = 0; i < ar.length; i++)
            for (int j = 0; j < ar[0].length; j++)
                nr[i][j] = ar[i][j];
        return nr;
    }

    /**
     * <h1>指定した値以上の先頭のインデクスを返す</h1>
     * <p>配列要素が0のときは、0が返る。</p>
     *
     * @return<b>int</b> : 探索した値以上で、先頭になるインデクス
     * 値が無ければ、挿入できる最小のインデックス
     */
    public static int lowerBound(final int[] arr, final int value)
    {
        int low = 0;
        int high = arr.length;
        int mid;

        while (low < high)
        {
            mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
            if (arr[mid] < value)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }
        return low;
    }

    /**
     * <h1>指定した値より大きい先頭のインデクスを返す</h1>
     * <p>配列要素が0のときは、0が返る。</p>
     *
     * @return<b>int</b> : 探索した値より上で、先頭になるインデクス
     * 値が無ければ、挿入できる最小のインデックス
     */
    public static int upperBound(final int[] arr, final int value)
    {
        int low = 0;
        int high = arr.length;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
            if (arr[mid] <= value)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }
        return low;
    }

    /**
     * <h1>指定した値以上の先頭のインデクスを返す</h1>
     * <p>配列要素が0のときは、0が返る。</p>
     *
     * @return<b>int</b> : 探索した値以上で、先頭になるインデクス
     * 値がなければ挿入できる最小のインデックス
     */
    public static long lowerBound(final long[] arr, final long value)
    {
        int low = 0;
        int high = arr.length;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
            if (arr[mid] < value)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }
        return low;
    }

    /**
     * <h1>指定した値より大きい先頭のインデクスを返す</h1>
     * <p>配列要素が0のときは、0が返る。</p>
     *
     * @return<b>int</b> : 探索した値より上で、先頭になるインデクス
     * 値がなければ挿入できる最小のインデックス
     */
    public static long upperBound(final long[] arr, final long value)
    {
        int low = 0;
        int high = arr.length;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
            if (arr[mid] <= value)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }
        return low;
    }

    //次の順列に書き換える、最大値ならfalseを返す
    public static boolean nextPermutation(int A[])
    {
        int len = A.length;
        int pos = len - 2;
        for (; pos >= 0; pos--)
        {
            if (A[pos] < A[pos + 1]) break;
        }
        if (pos == -1) return false;

        //posより大きい最小の数を二分探索
        int ok = pos + 1;
        int ng = len;
        while (Math.abs(ng - ok) > 1)
        {
            int mid = (ok + ng) / 2;
            if (A[mid] > A[pos]) ok = mid;
            else ng = mid;

        }

        swap(A, pos, ok);
        reverse(A, pos + 1, len - 1);


        return true;
    }

    //次の順列に書き換える、最小値ならfalseを返す
    public static boolean prevPermutation(int A[])
    {
        int len = A.length;
        int pos = len - 2;
        for (; pos >= 0; pos--)
        {
            if (A[pos] > A[pos + 1]) break;
        }
        if (pos == -1) return false;

        //posより小さい最大の数を二分探索
        int ok = pos + 1;
        int ng = len;
        while (Math.abs(ng - ok) > 1)
        {
            int mid = (ok + ng) / 2;
            if (A[mid] < A[pos]) ok = mid;
            else ng = mid;

        }

        swap(A, pos, ok);
        reverse(A, pos + 1, len - 1);


        return true;
    }

    //↓nCrをmod計算するために必要。 ***factorial(N)を呼ぶ必要がある***
    static long ncr(int n, int r)
    {
        if (n < r) return 0;
        else if (r == 0) return 1;

        factorial(n);
        return Fa[n] / (Fa[n - r] * Fa[r]);
    }

    static long ncr2(int a, int b)
    {
        if (b == 0) return 1;
        else if (a < b) return 0;
        long res = 1;
        for (int i = 0; i < b; i++)
        {
            res *= a - i;
            res /= i + 1;
        }
        return res;
    }

    static long ncrdp(int n, int r)
    {
        if (n < r) return 0;
        long[][] dp = new long[n + 1][r + 1];
        for (int ni = 0; ni < n + 1; ni++)
        {
            dp[ni][0] = dp[ni][ni] = 1;
            for (int ri = 1; ri < ni; ri++)
            {
                dp[ni][ri] = dp[ni - 1][ri - 1] + dp[ni - 1][ri];
            }
        }
        return dp[n][r];
    }

    static long modNcr(int n, int r)
    {
        if (n < r) return 0;
        long result = Fa[n];
        result = result * modInv(Fa[n - r]) % MOD;
        result = result * modInv(Fa[r]) % MOD;
        return result;
    }

    public static long modSum(long... lar)
    {
        long res = 0;
        for (long l : lar)
            res = (res + l % MOD) % MOD;
        if (res < 0) res += MOD;
        res %= MOD;
        return res;
    }

    public static long modDiff(long a, long b)
    {
        long res = a % MOD - b % MOD;
        if (res < 0) res += MOD;
        res %= MOD;
        return res;
    }

    public static long modMul(long... lar)
    {
        long res = 1;
        for (long l : lar)
            res = (res * l % MOD) % MOD;
        if (res < 0) res += MOD;
        res %= MOD;
        return res;
    }

    public static long modDiv(long a, long b)
    {
        long x = a % MOD;
        long y = b % MOD;
        long res = (x * modInv(y)) % MOD;
        return res;
    }

    static long modInv(long n)
    {
        return modPow(n, MOD - 2);
    }

    static void factorial(int n)
    {
        Fa = new long[n + 1];
        Fa[0] = Fa[1] = 1;

        for (int i = 2; i <= n; i++)
        {
            Fa[i] = (Fa[i - 1] * i) % MOD;
        }

    }

    static long modPow(long x, long n)
    {
        long res = 1L;
        while (n > 0)
        {
            if ((n & 1) == 1)
            {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    //↑nCrをmod計算するために必要

    static int gcd(int n, int r)
    {
        return r == 0 ? n : gcd(r, n % r);
    }

    static long gcd(long n, long r)
    {
        return r == 0 ? n : gcd(r, n % r);
    }

    static <T> void swap(T[] x, int i, int j)
    {
        T t = x[i];
        x[i] = x[j];
        x[j] = t;
    }

    static void swap(int[] x, int i, int j)
    {
        int t = x[i];
        x[i] = x[j];
        x[j] = t;
    }

    public static void reverse(int[] x)
    {
        int l = 0;
        int r = x.length - 1;
        while (l < r)
        {
            int temp = x[l];
            x[l] = x[r];
            x[r] = temp;
            l++;
            r--;
        }
    }

    public static void reverse(long[] x)
    {
        int l = 0;
        int r = x.length - 1;
        while (l < r)
        {
            long temp = x[l];
            x[l] = x[r];
            x[r] = temp;
            l++;
            r--;
        }
    }

    public static void reverse(char[] x)
    {
        int l = 0;
        int r = x.length - 1;
        while (l < r)
        {
            char temp = x[l];
            x[l] = x[r];
            x[r] = temp;
            l++;
            r--;
        }
    }

    public static void reverse(int[] x, int s, int e)
    {
        int l = s;
        int r = e;
        while (l < r)
        {
            int temp = x[l];
            x[l] = x[r];
            x[r] = temp;
            l++;
            r--;
        }
    }

    static int length(int a)
    {
        int cou = 0;
        while (a != 0)
        {
            a /= 10;
            cou++;
        }
        return cou;
    }

    static int length(long a)
    {
        int cou = 0;
        while (a != 0)
        {
            a /= 10;
            cou++;
        }
        return cou;
    }

    static int cou(boolean[] a)
    {
        int res = 0;
        for (boolean b : a)
        {
            if (b) res++;
        }
        return res;
    }

    static int cou(String s, char c)
    {
        int res = 0;
        for (char ci : s.toCharArray())
        {
            if (ci == c) res++;
        }
        return res;
    }

    static int countC2(char[][] a, char c)
    {
        int co = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                if (a[i][j] == c) co++;
        return co;
    }

    static int countI(int[] a, int key)
    {
        int co = 0;
        for (int i = 0; i < a.length; i++)
            if (a[i] == key) co++;
        return co;
    }

    static int countI(int[][] a, int key)
    {
        int co = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                if (a[i][j] == key) co++;
        return co;
    }

    static void fill(int[][] a, int v)
    {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                a[i][j] = v;
    }

    static void fill(char[][] a, char c)
    {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                a[i][j] = c;
    }

    static void fill(long[][] a, long v)
    {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                a[i][j] = v;
    }

    static void fill(int[][][] a, int v)
    {
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < a[0].length; j++)
                for (int k = 0; k < a[0][0].length; k++)
                    a[i][j][k] = v;
    }

    static int max(int... a)
    {
        int res = Integer.MIN_VALUE;
        for (int i : a)
        {
            res = Math.max(res, i);
        }
        return res;
    }

    static long min(long... a)
    {
        long res = Long.MAX_VALUE;
        for (long i : a)
        {
            res = Math.min(res, i);
        }
        return res;
    }

    static int max(int[][] ar)
    {
        int res = Integer.MIN_VALUE;
        for (int i[] : ar)
            res = Math.max(res, max(i));
        return res;
    }

    static int min(int... a)
    {
        int res = Integer.MAX_VALUE;
        for (int i : a)
        {
            res = Math.min(res, i);
        }
        return res;
    }


    static int min(int[][] ar)
    {
        int res = Integer.MAX_VALUE;
        for (int i[] : ar)
            res = Math.min(res, min(i));
        return res;
    }

    static int sum(int[] a)
    {
        int cou = 0;
        for (int i : a)
            cou += i;
        return cou;
    }

    static int abs(int a)
    {
        return Math.abs(a);
    }

    //FastScanner

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokenizer = null;

    public static String next()
    {
        if (tokenizer == null || !tokenizer.hasMoreTokens())
        {
            try
            {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e)
            {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    /*public String nextChar(){
        return (char)next()[0];
    }*/
    public static String nextLine()
    {
        if (tokenizer == null || !tokenizer.hasMoreTokens())
        {
            try
            {
                return reader.readLine();
            } catch (IOException e)
            {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public static long nl()
    {
        return Long.parseLong(next());
    }

    public static int ni()
    {
        return Integer.parseInt(next());
    }

    public static double nd()
    {
        return Double.parseDouble(next());
    }

    public static int[] nia(int n)
    {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = ni();
        }
        return a;
    }

    //1-index
    public static int[] niao(int n)
    {
        int[] a = new int[n + 1];
        for (int i = 1; i < n + 1; i++)
        {
            a[i] = ni();
        }
        return a;
    }

    public static int[] niad(int n)
    {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = ni() - 1;
        }
        return a;
    }

    public static int[][] nit(int h, int w)
    {
        int[][] a = new int[h][w];
        for (int hi = 0; hi < h; hi++)
        {
            for (int wi = 0; wi < w; wi++)
            {
                a[hi][wi] = ni();
            }
        }
        return a;
    }

    public static int[][] nitd(int h, int w)
    {
        int[][] a = new int[h][w];
        for (int hi = 0; hi < h; hi++)
        {
            for (int wi = 0; wi < w; wi++)
            {
                a[hi][wi] = ni() - 1;
            }
        }
        return a;
    }

    //複数の配列を受け取る
    public static void nia2(int[] a, int[] b, int[] c)
    {
        for (int i = 0; i < a.length; i++)
        {
            a[i] = ni();
            b[i] = ni();
            c[i] = ni();
        }
    }

    //複数の配列を受け取る
    public static void nia3(int[] a, int[] b, int[] c)
    {
        for (int i = 0; i < a.length; i++)
        {
            a[i] = ni();
            b[i] = ni();
            c[i] = ni();
        }
    }

    public static char[] nca(int n)
    {
        char[] a = next().toCharArray();

        return a;
    }

    public static char[][] nct(int h, int w)
    {
        char[][] a = new char[h][w];
        for (int i = 0; i < h; i++)
        {
            a[i] = next().toCharArray();
        }
        return a;
    }

    //スペースが入っている場合
    public static char[][] ncts(int h, int w)
    {
        char[][] a = new char[h][w];
        for (int i = 0; i < h; i++)
        {
            a[i] = nextLine().replace(" ", "").toCharArray();
        }
        return a;
    }

    public static char[][] nctp(int h, int w, char c)
    {
        char[][] a = new char[h + 2][w + 2];
        //char c = '*';
        int i;
        for (i = 0; i < w + 2; i++)
            a[0][i] = c;
        for (i = 1; i < h + 1; i++)
        {
            a[i] = (c + next() + c).toCharArray();
        }
        for (i = 0; i < w + 2; i++)
            a[h + 1][i] = c;
        return a;
    }

    //スペースが入ってる時用
    public static char[][] nctsp(int h, int w, char c)
    {
        char[][] a = new char[h + 2][w + 2];
        //char c = '*';
        int i;
        for (i = 0; i < w + 2; i++)
            a[0][i] = c;
        for (i = 1; i < h + 1; i++)
        {
            a[i] = (c + nextLine().replace(" ", "") + c).toCharArray();
        }
        for (i = 0; i < w + 2; i++)
            a[h + 1][i] = c;
        return a;
    }

    public static long[] nla(int n)
    {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = nl();
        }
        return a;
    }

    public static long[][] nlt(int h, int w)
    {
        long[][] a = new long[h][w];
        for (int hi = 0; hi < h; hi++)
        {
            for (int wi = 0; wi < w; wi++)
            {
                a[hi][wi] = nl();
            }
        }
        return a;
    }
}
0