Submission #2744487


Source Code Expand

Copy
lines = $stdin.read
INF = 100000000

array = lines.split("\n")
N = array[0].to_i
boxes = array[1..N].map do |str|
  arr = str.split(" ").map(&:to_i)
  Hash[*arr]
end.sort_by do |e|
  key,val = e.first
  [key,-val]
end

dp = Array.new(N,INF)
#p boxes

boxes.each_with_index do |m,i|
  k,v = m.first.to_a[0],m.first.to_a[1]
  idx = dp.bsearch_index do |h|
    v < h+1
  end
  if not idx.nil?
    dp[idx] = v
  end
end

#p dp
ans = dp.bsearch_index{|h| h == INF}
ans ||= N
puts ans

Submission Info

Submission Time
Task D - プレゼント
User hiroyuking
Language Ruby (2.3.3)
Score 100
Code Size 509 Byte
Status
Exec Time 894 ms
Memory 51960 KB

Compile Error

./Main.rb:18: warning: assigned but unused variable - k

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 30 / 30 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
All 70 / 70 sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt 7 ms 1788 KB
sample1.txt 7 ms 1788 KB
sample2.txt 7 ms 1788 KB
sample3.txt 7 ms 1788 KB
subtask0_0.txt 10 ms 1916 KB
subtask0_1.txt 7 ms 1788 KB
subtask0_10.txt 13 ms 2296 KB
subtask0_11.txt 13 ms 2296 KB
subtask0_12.txt 14 ms 2296 KB
subtask0_13.txt 15 ms 2296 KB
subtask0_14.txt 14 ms 2296 KB
subtask0_2.txt 8 ms 1788 KB
subtask0_3.txt 9 ms 1788 KB
subtask0_4.txt 12 ms 2296 KB
subtask0_5.txt 8 ms 1788 KB
subtask0_6.txt 13 ms 2296 KB
subtask0_7.txt 14 ms 2296 KB
subtask0_8.txt 13 ms 2296 KB
subtask0_9.txt 10 ms 1916 KB
subtask1_0.txt 530 ms 31096 KB
subtask1_1.txt 20 ms 2556 KB
subtask1_10.txt 661 ms 51192 KB
subtask1_11.txt 661 ms 51960 KB
subtask1_12.txt 885 ms 51960 KB
subtask1_13.txt 886 ms 51960 KB
subtask1_14.txt 894 ms 51960 KB
subtask1_2.txt 133 ms 9720 KB
subtask1_3.txt 833 ms 46384 KB
subtask1_4.txt 870 ms 51704 KB
subtask1_5.txt 118 ms 8996 KB
subtask1_6.txt 658 ms 34680 KB
subtask1_7.txt 327 ms 19704 KB
subtask1_8.txt 823 ms 46872 KB
subtask1_9.txt 399 ms 25836 KB