AtCoder Beginner Contest 005

Submission #1591148

Source codeソースコード

require 'pp'
N = gets.to_i
MAP = [nil] + N.times.map{ [nil] + gets.split.map(&:to_i) }
Q, *PS = readlines.map(&:to_i)

scores = Array.new(N*N + 1, 0)
sums = {}

N.downto(1) do |y1|
  N.downto(1) do |x1|
    y1.upto(N) do |y2|
      x1.upto(N) do |x2|
        sum = MAP[y1][x1]
        sum += sums[y1][x1+1][y2][x2] unless x1==x2
        sum += sums[y1+1][x1][y2][x1] unless y1==y2
        sums[y1] ||= {}
        sums[y1][x1] ||= {}
        sums[y1][x1][y2] ||= {}
        sums[y1][x1][y2][x2] = sum
        area = (x2-x1+1)*(y2-y1+1)
        scores[area] = sum if scores[area] < sum
      end
    end
  end
end

2.upto(N*N) do |i|
  scores[i] = scores[i-1] if scores[i] < scores[i-1]
end

PS.each do |pn|
  p scores[pn]
end

Submission

Task問題 D - おいしいたこ焼きの焼き方
User nameユーザ名 Yutaka Hara
Created time投稿日時
Language言語 Ruby (2.3.3)
Status状態 AC
Score得点 100
Source lengthソースコード長 758 Byte
File nameファイル名
Exec time実行時間 2043 ms
Memory usageメモリ使用量 123900 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 1079 ms 70524 KB
rand1.txt AC 612 ms 40828 KB
rand2.txt AC 969 ms 64892 KB
rand3.txt AC 210 ms 15740 KB
rand4.txt AC 15 ms 2428 KB
rand_max0.txt AC 1994 ms 123900 KB
rand_max1.txt AC 2034 ms 123900 KB
rand_max2.txt AC 2043 ms 123900 KB
rand_max3.txt AC 2007 ms 123900 KB
rand_max4.txt AC 2005 ms 123900 KB
s1.txt AC 11 ms 2044 KB
s2.txt AC 11 ms 2044 KB
sub0.txt AC 11 ms 2044 KB
sub1.txt AC 11 ms 2044 KB
sub2.txt AC 11 ms 2044 KB
sub_rand_max0.txt AC 11 ms 2044 KB
sub_rand_max1.txt AC 11 ms 2044 KB
sub_rand_max2.txt AC 11 ms 2044 KB
sub_rand_max3.txt AC 11 ms 2044 KB
sub_rand_min0.txt AC 11 ms 4092 KB