Submission #1021827
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[][] C = new long[51][51]; 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 (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] * comb >= INF) { 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 | 9443 Byte |
Status | WA |
Exec Time | 337 ms |
Memory | 32460 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 800 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
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 | 94 ms | 8272 KB |
hack_2.txt | AC | 95 ms | 8144 KB |
hack_3.txt | WA | 94 ms | 8020 KB |
hack_4.txt | AC | 95 ms | 8144 KB |
hack_5.txt | WA | 95 ms | 8276 KB |
sample_1.txt | AC | 95 ms | 8016 KB |
sample_2.txt | AC | 95 ms | 8016 KB |
sample_3.txt | AC | 95 ms | 8016 KB |
subtask_1_1.txt | AC | 96 ms | 8272 KB |
subtask_1_10.txt | AC | 94 ms | 8272 KB |
subtask_1_11.txt | AC | 194 ms | 32336 KB |
subtask_1_12.txt | AC | 99 ms | 8404 KB |
subtask_1_13.txt | AC | 101 ms | 8400 KB |
subtask_1_14.txt | WA | 97 ms | 8020 KB |
subtask_1_15.txt | AC | 199 ms | 32368 KB |
subtask_1_16.txt | AC | 186 ms | 17220 KB |
subtask_1_17.txt | AC | 183 ms | 17340 KB |
subtask_1_18.txt | AC | 200 ms | 32148 KB |
subtask_1_19.txt | WA | 96 ms | 8016 KB |
subtask_1_2.txt | AC | 94 ms | 8144 KB |
subtask_1_20.txt | AC | 99 ms | 8404 KB |
subtask_1_3.txt | AC | 96 ms | 8272 KB |
subtask_1_4.txt | AC | 99 ms | 8404 KB |
subtask_1_5.txt | AC | 99 ms | 8404 KB |
subtask_1_6.txt | AC | 111 ms | 8656 KB |
subtask_1_7.txt | AC | 111 ms | 8660 KB |
subtask_1_8.txt | AC | 196 ms | 32328 KB |
subtask_1_9.txt | AC | 155 ms | 17212 KB |
subtask_2_1.txt | AC | 117 ms | 10192 KB |
subtask_2_10.txt | AC | 123 ms | 11272 KB |
subtask_2_11.txt | AC | 155 ms | 17216 KB |
subtask_2_12.txt | AC | 182 ms | 32460 KB |
subtask_2_13.txt | WA | 151 ms | 21176 KB |
subtask_2_14.txt | AC | 337 ms | 32348 KB |
subtask_2_15.txt | AC | 96 ms | 8404 KB |
subtask_2_16.txt | AC | 142 ms | 17212 KB |
subtask_2_17.txt | AC | 142 ms | 17344 KB |
subtask_2_18.txt | AC | 161 ms | 22584 KB |
subtask_2_19.txt | WA | 97 ms | 8272 KB |
subtask_2_2.txt | AC | 142 ms | 21312 KB |
subtask_2_20.txt | AC | 96 ms | 8272 KB |
subtask_2_21.txt | AC | 97 ms | 8272 KB |
subtask_2_22.txt | AC | 95 ms | 8276 KB |
subtask_2_23.txt | AC | 96 ms | 8272 KB |
subtask_2_24.txt | AC | 97 ms | 8148 KB |
subtask_2_25.txt | AC | 97 ms | 8272 KB |
subtask_2_26.txt | AC | 97 ms | 8276 KB |
subtask_2_27.txt | AC | 99 ms | 8400 KB |
subtask_2_3.txt | AC | 153 ms | 21560 KB |
subtask_2_4.txt | AC | 131 ms | 15312 KB |
subtask_2_5.txt | AC | 183 ms | 32368 KB |
subtask_2_6.txt | AC | 156 ms | 17344 KB |
subtask_2_7.txt | AC | 137 ms | 14160 KB |
subtask_2_8.txt | AC | 107 ms | 9428 KB |
subtask_2_9.txt | AC | 125 ms | 11856 KB |
subtask_3_1.txt | AC | 103 ms | 8524 KB |
subtask_3_10.txt | AC | 190 ms | 21308 KB |
subtask_3_11.txt | AC | 192 ms | 21060 KB |
subtask_3_12.txt | AC | 187 ms | 17216 KB |
subtask_3_13.txt | WA | 106 ms | 8276 KB |
subtask_3_14.txt | WA | 107 ms | 8276 KB |
subtask_3_2.txt | AC | 112 ms | 8784 KB |
subtask_3_3.txt | AC | 227 ms | 32400 KB |
subtask_3_4.txt | AC | 200 ms | 17340 KB |
subtask_3_5.txt | AC | 201 ms | 21816 KB |
subtask_3_6.txt | AC | 210 ms | 17404 KB |
subtask_3_7.txt | WA | 200 ms | 21188 KB |
subtask_3_8.txt | WA | 194 ms | 18620 KB |
subtask_3_9.txt | AC | 201 ms | 22076 KB |