Submission #1961658


Source Code Expand

Copy
lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
D = array[1..N].map{|s| s.split(" ").map(&:to_i)}
Q = array[N+1].to_i
P = array[N+2..Q+N+1].map(&:to_i)

I = J = W = H = N

dp = Array.new(I).map{
  Array.new(J).map{
    Array.new(W).map{
      Array.new(H, 0)
    }
  }
}

max_v = {}

for i in 0..N-1
  for j in 0..N-1
    dp[i][j][0][0] = D[i][j]
    max_v[1] = dp[i][j][0][0] if max_v[1].to_i < dp[i][j][0][0]
  end
end

for i in 0..N-1
  for j in 0..N-1
    for h in 1...N-i
      dp[i][j][0][h] = dp[i][j][0][h-1] + dp[i+h][j][0][0]
      max_v[h+1] = dp[i][j][0][h] if max_v[h+1].to_i < dp[i][j][0][h]
      #puts "dp[#{i}][#{j}][0][#{h}] = #{dp[i][j][0][h]}"
    end
    for w in 1...N-j
      dp[i][j][w][0] = dp[i][j][w-1][0] + dp[i][j+w][0][0]
      max_v[w+1] = dp[i][j][w][0] if max_v[w+1].to_i < dp[i][j][w][0]
      #puts "dp[#{i}][#{j}][#{w}][0] = #{dp[i][j][w][0]}"
    end
  end
end


for i in 0..N-1
  for j in 0..N-1
    for h in 1...N-i
      for w in 1...N-j
        dp[i][j][w][h] = dp[i][j][w-1][h] + dp[i][j+w][0][h]
        max_v[(w+1)*(h+1)] = dp[i][j][w][h].to_i if max_v[(w+1)*(h+1)].to_i < dp[i][j][w][h].to_i
        #puts "dp[#{i}][#{j}][#{w}][#{h}] = #{dp[i][j][w][h]}"
      end
    end
  end
end

P.each do |ps|
   puts max_v.select{|k,v| k <= ps}.max_by{|k,v| v}.last
end

Submission Info

Submission Time
Task D - おいしいたこ焼きの焼き方
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 1378 Byte
Status
Exec Time 1786 ms
Memory 76924 KB

Test Cases

Set Name Score / Max Score Test 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
Case Name Status Exec Time Memory
rand0.txt 611 ms 39548 KB
rand1.txt 446 ms 24316 KB
rand2.txt 833 ms 39548 KB
rand3.txt 137 ms 10620 KB
rand4.txt 12 ms 2044 KB
rand_max0.txt 1786 ms 76796 KB
rand_max1.txt 1758 ms 76796 KB
rand_max2.txt 1767 ms 76924 KB
rand_max3.txt 1745 ms 76796 KB
rand_max4.txt 1747 ms 76796 KB
s1.txt 8 ms 1788 KB
s2.txt 8 ms 1788 KB
sub0.txt 8 ms 1788 KB
sub1.txt 8 ms 1788 KB
sub2.txt 8 ms 1788 KB
sub_rand_max0.txt 8 ms 1788 KB
sub_rand_max1.txt 8 ms 1788 KB
sub_rand_max2.txt 8 ms 1788 KB
sub_rand_max3.txt 8 ms 1788 KB
sub_rand_min0.txt 7 ms 1788 KB