fork download
  1. # paiza POH! Vol.1
  2. # result:
  3. # http://p...content-available-to-author-only...a.jp/poh/ec-campaign/result/dcb4fefe9a664bb385df949cf057122e
  4. # author: Leonardone @ NEETSDKASU
  5.  
  6. def foo(p, f, e, m)
  7. df = e - f
  8. if df < 5 then
  9. f
  10. else
  11. ci = f + (df >> 1)
  12. if m > p[ci] then
  13. foo(p, ci, e, m)
  14. else
  15. foo(p, f, ci, m)
  16. end
  17. end
  18. end
  19.  
  20. def bar(p, f, e, m)
  21. df = e - f
  22. if df < 5 then
  23. e
  24. else
  25. ci = f + (df >> 1)
  26. if m < p[ci] then
  27. bar(p, f, ci, m)
  28. else
  29. bar(p, ci, e, m)
  30. end
  31. end
  32. end
  33.  
  34.  
  35. s = gets.split(' ')
  36. n = s[0].to_i
  37. d = s[1].to_i
  38. p = []
  39. n.times do |i|
  40. p[i] = gets.to_i
  41. end
  42. p = p.sort
  43.  
  44. d.times do
  45. m = gets.to_i
  46. tmp = 0
  47. j = bar(p, 0, n - 1, m)
  48. while (j >= 0) && (p[j] >= m) do
  49. j = j - 1
  50. end
  51. if j >=0 then
  52. df = m - p[j]
  53. if df <= p[j] then
  54. i = foo(p, 0, j, df)
  55. while df <= p[j] do
  56. while (df > p[i]) do
  57. i = i + 1
  58. end
  59. if (df < p[i]) || (i == j) then
  60. if i > 0 then
  61. i = i - 1
  62. end
  63. end
  64. sum = p[i] + p[j]
  65. if (sum > tmp) && (sum <= m) then
  66. tmp = sum
  67. if tmp == m then
  68. break
  69. end
  70. end
  71. j = j - 1
  72. df = m - p[j]
  73. end
  74. end
  75. end
  76. puts tmp
  77. end
Success #stdin #stdout 0.01s 7412KB
stdin
10 6
4500
13300
1100
2200
25100
4000
3000
1000
2000
5000
15000
3000
10000
30000
4000
5600
stdout
14400
3000
9500
29600
4000
5600