Submission #1021831


Source Code Expand

// package atcoder.other2016.codefestival2016.round2;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
    private static final long INF = (long) 4e9;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();

        long[][] table = in.nextLongTable(n, m);



        long sum = 0;
        long last = 0;
        for (int i = 0; i+1 < n; i++) {
            int k = -1;
            for (int j = 0; j < m ; j++) {
                if (table[i][j] == table[i+1][j]) {
                    continue;
                } else {
                    k = j;
                    break;
                }
            }
            if (m == 1) {
                if (table[i][0] < table[i+1][0]) {
                    // ok
                } else {
                    sum = -1;
                    break;
                }
                continue;
            }

            if (k == -1) {
                // completely same.
                sum += last+1;
                last = last+1;
            } else if (k == 0) {
                // different at first.
                if (table[i][k] < table[i+1][k]) {
                    last = 0;
                } else {
                    // NG
                    sum = -1;
                    break;
                }
            } else {
                // how many func required actually?
                long head = table[i][0];
                long second = head * last + table[i][1];
                if (second < table[i+1][1]) {
                    last = 0;
                    continue;
                }
                long req = (second - table[i+1][1] + head - 1) / head;
                long tos = head * req + table[i][1];
                if (second < tos) {
                    sum += req;
                    last = req;
                    continue;
                }

                // operation required: req or req+1 times.
                if (compare(table[i], last, table[i+1], req) == -1) {
                    sum += req;
                    last = req;
                } else {
                    sum += req+1;
                    last = req+1;
                }
            }
        }

        out.println(sum);
        out.flush();
    }

    private static int compare(long[] a, long opA, long[] b, long opB) {
        if (opA == 0) {
            return compare(a, b, opB);
        } else if (opB == 0) {
            return -compare(b, opB, a, opA);
        } else {
            long dec = Math.min(opA, opB);
            return compare(a, opA-dec, b, opB-dec);
        }
    }

    private static int compare(long[] a, long[] b, long opB) {
        int n = b.length;
        long[] tob = b.clone();
        if (opB <= 32) {
            for (int f = 0 ; f < opB ; f++) {
                operate(tob);
            }
            for (int i = 0 ; i < n ; i++) {
                if (a[i] != tob[i]) {
                    return (a[i] < tob[i]) ? -1 : 1;
                }
            }
        } else {
            for (int k = 1 ; k < n ; k++) {
                long sum = 0;
                int d = 0;
                for (int part = k ; part >= 0 ; part--) {
                    long left = opB+d-1;
                    long right = d;
                    long comb = comb(left, right);
                    if (comb >= INF || b[part] >= INF / comb) {
                        sum = INF;
                        break;
                    }
                    sum += b[part] * comb;
                    if (sum >= INF) {
                        sum = INF;
                        break;
                    }
                    d++;
                }
                tob[k] = sum;
                if (a[k] != tob[k]) {
                    return (a[k] < tob[k]) ? -1 : 1;
                }
            }
        }
        return 0;
    }

    static final int MOD = 1000000007;

    static long pow(long a, long x) {
        long res = 1;
        while (x > 0) {
            if (x%2 != 0) {
                res = (res*a)%MOD;
            }
            a = (a*a)%MOD;
            x /= 2;
        }
        return res;
    }


    static long comb(long n, long r) {
        BigInteger up = BigInteger.ONE;
        BigInteger dw = BigInteger.ONE;
        for (int i = 0; i < r ; i++) {
            up = up.multiply(BigInteger.valueOf(n-i));
            dw = dw.multiply(BigInteger.valueOf(i+1));
        }
        BigInteger ret = up.divide(dw);
        if (ret.compareTo(BigInteger.valueOf(INF)) == -1) {
            return ret.longValue();
        }
        return INF;
    }


    private static void operate(long[] a) {
        long psum = a[0];
        for (int i = 1  ; i < a.length ; i++) {
            psum += a[i];
            if (psum >= INF) {
                psum = INF;
            }
            a[i] = psum;
        }
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int[] nextInts(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        private int[][] nextIntTable(int n, int m) {
            int[][] ret = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextInt();
                }
            }
            return ret;
        }

        private long[] nextLongs(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

        private long[][] nextLongTable(int n, int m) {
            long[][] ret = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextLong();
                }
            }
            return ret;
        }

        private double[] nextDoubles(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextDouble();
            }
            return ret;
        }

        private int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            if ('a' <= c && c <= 'z') {
                return (char) c;
            }
            if ('A' <= c && c <= 'Z') {
                return (char) c;
            }
            throw new InputMismatchException();
        }

        public String nextToken() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}

Submission Info

Submission Time
Task B - Takahashi the Magician
User hamadu
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 9655 Byte
Status WA
Exec Time 224 ms
Memory 32388 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 800 0 / 200
Status
AC × 3
AC × 22
WA × 5
AC × 31
WA × 4
AC × 60
WA × 9
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
Case Name Status Exec Time Memory
hack_1.txt WA 93 ms 8144 KB
hack_2.txt AC 93 ms 8148 KB
hack_3.txt WA 93 ms 8148 KB
hack_4.txt AC 93 ms 8148 KB
hack_5.txt WA 202 ms 8148 KB
sample_1.txt AC 92 ms 8148 KB
sample_2.txt AC 94 ms 8144 KB
sample_3.txt AC 95 ms 8016 KB
subtask_1_1.txt AC 95 ms 8276 KB
subtask_1_10.txt AC 94 ms 8276 KB
subtask_1_11.txt AC 193 ms 32364 KB
subtask_1_12.txt AC 98 ms 8404 KB
subtask_1_13.txt AC 97 ms 8276 KB
subtask_1_14.txt WA 93 ms 8020 KB
subtask_1_15.txt AC 195 ms 32128 KB
subtask_1_16.txt AC 183 ms 17220 KB
subtask_1_17.txt AC 184 ms 17344 KB
subtask_1_18.txt AC 196 ms 32248 KB
subtask_1_19.txt WA 94 ms 8016 KB
subtask_1_2.txt AC 94 ms 8020 KB
subtask_1_20.txt AC 106 ms 8276 KB
subtask_1_3.txt AC 95 ms 8276 KB
subtask_1_4.txt AC 97 ms 8272 KB
subtask_1_5.txt AC 97 ms 8276 KB
subtask_1_6.txt AC 110 ms 8784 KB
subtask_1_7.txt AC 110 ms 8784 KB
subtask_1_8.txt AC 195 ms 32244 KB
subtask_1_9.txt AC 144 ms 17088 KB
subtask_2_1.txt AC 109 ms 9940 KB
subtask_2_10.txt AC 110 ms 10964 KB
subtask_2_11.txt AC 153 ms 17216 KB
subtask_2_12.txt AC 177 ms 32376 KB
subtask_2_13.txt WA 148 ms 21180 KB
subtask_2_14.txt AC 182 ms 32280 KB
subtask_2_15.txt AC 96 ms 8404 KB
subtask_2_16.txt AC 139 ms 17216 KB
subtask_2_17.txt AC 136 ms 17208 KB
subtask_2_18.txt AC 161 ms 22468 KB
subtask_2_19.txt AC 95 ms 8272 KB
subtask_2_2.txt AC 144 ms 21328 KB
subtask_2_20.txt AC 95 ms 8272 KB
subtask_2_21.txt AC 95 ms 8148 KB
subtask_2_22.txt AC 97 ms 8144 KB
subtask_2_23.txt AC 97 ms 8272 KB
subtask_2_24.txt AC 95 ms 8276 KB
subtask_2_25.txt AC 95 ms 8276 KB
subtask_2_26.txt AC 105 ms 8276 KB
subtask_2_27.txt AC 98 ms 8276 KB
subtask_2_3.txt AC 137 ms 21436 KB
subtask_2_4.txt AC 130 ms 15316 KB
subtask_2_5.txt AC 179 ms 32388 KB
subtask_2_6.txt AC 151 ms 17336 KB
subtask_2_7.txt AC 145 ms 14160 KB
subtask_2_8.txt AC 112 ms 9296 KB
subtask_2_9.txt AC 125 ms 11856 KB
subtask_3_1.txt AC 100 ms 8652 KB
subtask_3_10.txt AC 191 ms 21316 KB
subtask_3_11.txt AC 188 ms 21184 KB
subtask_3_12.txt AC 183 ms 17216 KB
subtask_3_13.txt WA 97 ms 8276 KB
subtask_3_14.txt AC 97 ms 8404 KB
subtask_3_2.txt AC 111 ms 9044 KB
subtask_3_3.txt AC 224 ms 32248 KB
subtask_3_4.txt AC 197 ms 17344 KB
subtask_3_5.txt AC 201 ms 21824 KB
subtask_3_6.txt AC 198 ms 17220 KB
subtask_3_7.txt WA 197 ms 21188 KB
subtask_3_8.txt WA 191 ms 18496 KB
subtask_3_9.txt AC 200 ms 22208 KB