Submission #27281255

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N,*A = $<.read.split.map(&:to_i)
S = A.sum
W = S/[N-2,1].max+1
Sr = 102.times.map{ Math.sqrt _1*_1+1 }
D = Array.new(N){ Array.new(S+1){ [1.0/0]*(S+1) } }
D[0][S][0] = 0 # i=0 時点で残りが A.sum で Ai の値が 0 の場合の操作の最小が 0
D.each_cons(2){|d0,d|
  d0.each_with_index{|d0,b0|
    d0.each_with_index{|s0,a0|
      [a0-W,0].max.upto([a0+W,b0].min){|a|
        b = b0-a
        s = s0+Sr[(a-a0).abs]
        d[b][a] = s if s<d[b][a]
      }
    }
  }
}
p D[-1][0][0]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,*A = $<.read.split.map(&:to_i)
S = A.sum
W = S/[N-2,1].max+1
Sr = 102.times.map{ Math.sqrt _1*_1+1 }

D = Array.new(N){ Array.new(S+1){ [1.0/0]*(S+1) } }
D[0][S][0] = 0 # i=0 時点で残りが A.sum で Ai の値が 0 の場合の操作の最小が 0
D.each_cons(2){|d0,d|
	d0.each_with_index{|d0,b0|
		d0.each_with_index{|s0,a0|
			[a0-W,0].max.upto([a0+W,b0].min){|a|
				b = b0-a
				s = s0+Sr[(a-a0).abs]
				d[b][a] = s if s<d[b][a]
			}
		}
	}
}
p D[-1][0][0]

Submission Info

Judge Result