AtCoder Beginner Contest 005

Submission #6909027

Source codeソースコード

/**
 * 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

Task問題 D - おいしいたこ焼きの焼き方
User nameユーザ名 yutake
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 6148 Byte
File nameファイル名
Exec time実行時間 133 ms
Memory usageメモリ使用量 22808 KB

Compiler messageコンパイルメッセージ

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Test case

Set

Set name Score得点 / Max score Cases
Subtask1 50 / 50 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 50 / 50 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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