Submission #6909027
Source Code Expand
/** * Created at 02:02 on 2019-08-15 */ import java.io.*; import java.util.*; public class Main { static FastScanner sc = new FastScanner(); static Output out = new Output(System.out); static final int[] dx = {0, 1, 0, -1}; static final int[] dy = {-1, 0, 1, 0}; static final long MOD = (long) (1e9 + 7); static final long INF = Long.MAX_VALUE / 2; public static class Solver { public Solver() { int N = sc.nextInt(); long[][] D = new long[N][N]; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { D[i][j] = sc.nextLong(); } } long[][] cumsum = new long[N+1][N+1]; for (int i=1; i<=N; i++) { for (int j=1; j<=N; j++) { cumsum[i][j] = cumsum[i-1][j] + cumsum[i][j-1] - cumsum[i-1][j-1] + D[i-1][j-1]; } } long[] ans = new long[N*N+1]; for (int i=1; i<=N*N; i++) { int[] factors = getFactors(i); for (int j=0; j<factors.length; j++) { int w = factors[j]; int h = i / w; //右下座標 for (int x=w; x<=N; x++) { for (int y=h; y<=N; y++) { ans[i] = Math.max(ans[i], cumsum[x][y] - cumsum[x-w][y] - cumsum[x][y-h] + cumsum[x-w][y-h]); } } } } for (int i=1; i<=N*N; i++) { ans[i] = Math.max(ans[i], ans[i-1]); } int Q = sc.nextInt(); for (int q=0; q<Q; q++) { int p = sc.nextInt(); out.println(ans[p]); } } /* * 約数を小さい順に並べた配列を返す */ public int[] getFactors(int n) { ArrayList<Integer> f1 = new ArrayList(); ArrayList<Integer> f2 = new ArrayList(); int bound = (int)Math.sqrt(n); for (int i=1; i<=bound; i++) { if (n % i == 0) { f1.add(i); f2.add(n/i); } } if (bound * bound == n) f2.remove(f2.size()-1); int[] factors = new int[f1.size() + f2.size()]; for (int i=0; i<f1.size(); i++) { factors[i] = f1.get(i); } for (int i=0; i<f2.size(); i++) { factors[f1.size()+i] = f2.get(f2.size()-i-1); } return factors; } } public static void main(String[] args) { new Solver(); out.flush(); } static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int N, boolean oneBased) { if (oneBased) { int[] array = new int[N + 1]; for (int i = 1; i <= N; i++) { array[i] = sc.nextInt(); } return array; } else { int[] array = new int[N]; for (int i = 0; i < N; i++) { array[i] = sc.nextInt(); } return array; } } public long[] nextLongArray(int N, boolean oneBased) { if (oneBased) { long[] array = new long[N + 1]; for (int i = 1; i <= N; i++) { array[i] = sc.nextLong(); } return array; } else { long[] array = new long[N]; for (int i = 0; i < N; i++) { array[i] = sc.nextLong(); } return array; } } } static class Output extends PrintWriter { public Output(PrintStream ps) { super(ps); } public void print(int[] a, String separator) { for (int i = 0; i < a.length; i++) { if (i == 0) print(a[i]); else print(separator + a[i]); } println(); } public void print(long[] a, String separator) { for (int i = 0; i < a.length; i++) { if (i == 0) print(a[i]); else print(separator + a[i]); } println(); } public void print(String[] a, String separator) { for (int i = 0; i < a.length; i++) { if (i == 0) print(a[i]); else print(separator + a[i]); } println(); } public void print(ArrayList a, String separator) { for (int i = 0; i < a.size(); i++) { if (i == 0) print(a.get(i)); else print(separator + a.get(i)); } println(); } } }
Submission Info
Submission Time | |
---|---|
Task | D - おいしいたこ焼きの焼き方 |
User | yutake2000 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 6148 Byte |
Status | AC |
Exec Time | 133 ms |
Memory | 22808 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Subtask2 | rand0.txt, rand1.txt, rand2.txt, rand3.txt, rand4.txt, rand_max0.txt, rand_max1.txt, rand_max2.txt, rand_max3.txt, rand_max4.txt, s1.txt, s2.txt, sub0.txt, sub1.txt, sub2.txt, sub_rand_max0.txt, sub_rand_max1.txt, sub_rand_max2.txt, sub_rand_max3.txt, sub_rand_min0.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
rand0.txt | AC | 104 ms | 20564 KB |
rand1.txt | AC | 117 ms | 21844 KB |
rand2.txt | AC | 118 ms | 19656 KB |
rand3.txt | AC | 104 ms | 22484 KB |
rand4.txt | AC | 72 ms | 21332 KB |
rand_max0.txt | AC | 125 ms | 22808 KB |
rand_max1.txt | AC | 124 ms | 22560 KB |
rand_max2.txt | AC | 128 ms | 22476 KB |
rand_max3.txt | AC | 133 ms | 20744 KB |
rand_max4.txt | AC | 127 ms | 21344 KB |
s1.txt | AC | 69 ms | 18516 KB |
s2.txt | AC | 70 ms | 19540 KB |
sub0.txt | AC | 71 ms | 20820 KB |
sub1.txt | AC | 70 ms | 19412 KB |
sub2.txt | AC | 71 ms | 18644 KB |
sub_rand_max0.txt | AC | 72 ms | 19284 KB |
sub_rand_max1.txt | AC | 71 ms | 18644 KB |
sub_rand_max2.txt | AC | 70 ms | 21460 KB |
sub_rand_max3.txt | AC | 70 ms | 21460 KB |
sub_rand_min0.txt | AC | 71 ms | 19412 KB |