1)use a tricky segment_tree instead of a prefix, but I'm too lazy to think

2)**O(N*W^2)**(for little W)

We calculate dp from two sides (prefix and suffix) then the answer is without i block = prefix[i-1] # suffix[i+1] //O(W^2)

try for each achievable value add 20-% or 80+%

maybe # == * and it can be reduced to FFT(O(wlogw)), but I'm not so strong

https://pastebin.com/K4yrQjCe

not particularly verified

ok, dp[1][i][j] — double

dp[1][i][j] == -1 if unattainable value,else dp[1][i][j] == x =[0,1] — fractional part. if segment(l+1, r)==true -> x=1 else if dp[0][i-1][l] -> x = fractional part a[i]*y%.

found O(NW)

just count 2 dp: the first is normal dp[0], the second using separation dp[1]

then dp[1][i][j] = dp[1][i-1][j] or dp[1][i-1][j-arr[i]] or (dp[0][i-1][j-x]) or (dp[0][i-1][j-y]):

x = (0-20%) * a[i] : X = (j- a[i]*0.2, j )

y = (80-100%) * a[i] : Y = (j — a[i], j — a[i]*0.8)

to find out if on segment X or Y true, you can use prefix sum

(sorry, translate.google)