fork download
copy 
  1. n,m,k=gets.split(" ").map{|e| e.to_i}
  2. data=[]
  3. dp=[10**31]*(n+2)
  4. n.times{
  5. 	data<<gets.to_i
  6. }
  7. dp[0]=0
  8. n.times{|i|
  9. 	j=i
  10. 	min1=data[i]
  11. 	max1=data[i]
  12. 	while j<n && j<i+m
  13. 		min1=[min1,data[j]].min
  14. 		max1=[max1,data[j]].max
  15. 		t=(j-i+1)*(max1-min1)+k+dp[i]
  16. 		dp[j+1]=[dp[j+1],t].min
  17. 		j+=1
  18. 	end
  19. }
  20. puts dp[n]
Success #stdin #stdout 0.01s 8108KB
comments (?)
stdin
copy 
16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19
stdout
copy 
164
https://ideone.com/lXTiEx
language:
Ruby (ruby 2.5.5)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!