結果
問題 | No.1536 仕切り直し |
ユーザー | yuruhiya |
提出日時 | 2021-07-16 15:39:59 |
言語 | Crystal (1.11.2) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 3,116 bytes |
コンパイル時間 | 12,830 ms |
コンパイル使用メモリ | 295,928 KB |
実行使用メモリ | 76,388 KB |
最終ジャッジ日時 | 2024-07-06 01:47:47 |
合計ジャッジ時間 | 14,016 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 6 ms
6,784 KB |
testcase_04 | AC | 27 ms
28,928 KB |
testcase_05 | AC | 48 ms
54,016 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,888 KB |
testcase_08 | AC | 23 ms
23,296 KB |
testcase_09 | AC | 31 ms
37,376 KB |
testcase_10 | AC | 67 ms
76,388 KB |
testcase_11 | AC | 18 ms
18,816 KB |
testcase_12 | AC | 52 ms
65,188 KB |
ソースコード
# require "/scanner" class Scanner private def self.skip_to_not_space peek = STDIN.peek not_space = peek.index { |x| x != 32 && x != 10 } || peek.size STDIN.skip(not_space) end def self.c skip_to_not_space STDIN.read_char.not_nil! end def self.s skip_to_not_space peek = STDIN.peek if index = peek.index { |x| x == 32 || x == 10 } STDIN.skip(index + 1) return String.new(peek[0, index]) end String.build do |buffer| loop do buffer.write peek STDIN.skip(peek.size) peek = STDIN.peek break if peek.empty? if index = peek.index { |x| x == 32 || x == 10 } buffer.write peek[0, index] STDIN.skip(index) break end end end end end macro internal_input(s, else_ast) {% if Scanner.class.has_method?(s.id) %} Scanner.{{s.id}} {% elsif s.stringify == "String" %} Scanner.s {% elsif s.stringify == "Char" %} Scanner.c {% elsif s.stringify =~ /[A-Z][a-z0-9_]*/ %} {{s.id}}.new(Scanner.s) {% elsif String.has_method?("to_#{s}".id) %} Scanner.s.to_{{s.id}} {% else %} {{else_ast}} {% end %} end macro internal_input_array(s, args, else_ast) {% if Scanner.class.has_method?(s.id) || s.stringify =~ /[A-Z][a-z0-9_]*/ || String.has_method?("to_#{s}".id) %} Array.new({{args.first}}) do {% if args.size == 1 %} input({{s.id}}) {% else %} internal_input_array({{s}}, {{args[1...args.size]}}, else_ast) {% end %} end {% else %} {{else_ast}} {% end %} end macro input(s) {% if s.is_a?(Call) %} {% if s.receiver.is_a?(Nop) %} internal_input( {{s.name}}, {{s.name}}( {% for argument in s.args %} input({{argument}}), {% end %} ) ) {% elsif s.name.stringify == "[]" %} internal_input_array( {{s.receiver}}, {{s.args}}, {{s.receiver}}[ {% for argument in s.args %} input({{argument}}), {% end %} ] {{s.block}} ) {% else %} input({{s.receiver}}).{{s.name.id}}( {% for argument in s.args %} input({{argument}}), {% end %} ) {{s.block}} {% end %} {% else %} internal_input({{s.id}}, {{s.id}}) {% end %} end macro input(*s) { {% for s in s %} input({{s}}), {% end %} } end n, m = input(i, i) a = input(i64[n]) dp = Array.new(n + 1) { Array.new(m.succ, -10i64**17) } prev = Array.new(n + 1) { Array({Int32, Int32}?).new(m.succ, nil) } dp[0][0] = 0 (0..n).each do |i| (0..m).each do |j| if dp[i][j] < dp[i - 1][j] + (j.even? ? +a[i - 1] : -a[i - 1]) dp[i][j] = dp[i - 1][j] + (j.even? ? +a[i - 1] : -a[i - 1]) prev[i][j] = {i - 1, j} end end if i > 0 (0...m).each do |j| if dp[i][j + 1] < dp[i][j] dp[i][j + 1] = dp[i][j] prev[i][j + 1] = {i, j} end end end ans = [] of Int32 pos = {n, m} while next_pos = prev.dig *pos if pos[0] == next_pos[0] ans << pos[0] end pos = next_pos end puts ans.reverse.join('\n')