AtCoder Beginner Contest 005

Submission #1591219

Source codeソースコード

require "pp"
N = gets.to_i
D = N.times.map do
  gets.split.map(&:to_i)
end
Q = gets.to_i
P = Q.times.map do
  gets.to_i
end

memo = []
memo2 = {}

P.each do |p|
  if memo[p]
    puts memo[p]
    next
  end

  pairs = (1..p).select { |i| p / i <= N && i <= N }.map do |n|
    [[n, p / n], [p / n, n]]
  end.flatten(1)

  pairs.each do |p1, p2|
    if memo2[[p1, p2]]
      next
    end

    # 行方向の圧縮
    a = Array.new(N) do
      Array.new(N - p1 + 1, 0)
    end
    N.times do |i|
      a[i][0] = D[i][0, p1].inject(:+)
      (N - p1).times do |j|
        a[i][j + 1] = a[i][j] + D[i][j + p1] - D[i][j]
      end
    end

    # 列方向の圧縮
    b = Array.new(N) do
      Array.new(N, 0)
    end
    (N - p1 + 1).times do |i|
      b[0][i] = a[0, p2].map { |c| c[i] }.inject(:+)
      (N - p2).times do |j|
        b[j + 1][i] = b[j][i] + a[j + p2][i] - a[j][i]
      end
    end
    max = b.map(&:max).max
    memo2[[p1, p2]] = max
  end

  p pairs.map { |i| memo2[i] }.max
end

Submission

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

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 1108 ms 3324 KB
rand1.txt AC 779 ms 3068 KB
rand2.txt AC 1391 ms 3196 KB
rand3.txt AC 251 ms 2940 KB
rand4.txt AC 19 ms 2428 KB
rand_max0.txt AC 2684 ms 3452 KB
rand_max1.txt AC 2681 ms 5500 KB
rand_max2.txt AC 2699 ms 3580 KB
rand_max3.txt AC 2698 ms 3452 KB
rand_max4.txt AC 2695 ms 3452 KB
s1.txt AC 11 ms 2044 KB
s2.txt AC 11 ms 2044 KB
sub0.txt AC 11 ms 2172 KB
sub1.txt AC 11 ms 2172 KB
sub2.txt AC 11 ms 2172 KB
sub_rand_max0.txt AC 12 ms 2172 KB
sub_rand_max1.txt AC 12 ms 2172 KB
sub_rand_max2.txt AC 12 ms 2172 KB
sub_rand_max3.txt AC 12 ms 2172 KB
sub_rand_min0.txt AC 10 ms 2044 KB