fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD (ll)(1e9+7)
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=1e4;
  18. int a[Max_n+3];
  19. ll dp[Max_n+3];
  20. void solve(){
  21. 	for (int i = 1 ; i <= Max_n ; i ++ )
  22. 		dp[i] = 1e18;
  23. 	int n ; cin >> n ; 
  24. 	int d , h ; cin >> d >> h ;
  25. 	for (int i = 1 ; i <= n ; i ++ ){
  26. 		cin >> a[i] ;
  27. 	}
  28. 	dp[1] = a[1] ;
  29. 	for (int i = 1 ; i <= n ; i ++ ){ 
  30. 		// i - j <= d
  31. 		// j >= d - i
  32. 		// i - d - i = d  
  33. 		// j = i + d 
  34. 		// i + d - i = d
  35. 		// i - j = 1 , j = i
  36. 		// i - j = d , j = i -d 
  37. 		for (int j = max(1,i-d)  ; j < i; j ++ ){
  38. 			if ( i - j <= d ) {
  39. 				if ( a[j] - a[i] <= h) dp[i] = min ( dp[i] , dp[j] + a[i]);
  40. 			}
  41. 		}
  42. 	}
  43. 	if ( dp[n] == 1e18||dp[n]==0) {
  44. 		cout << -1 ;
  45. 		return;
  46. 	}
  47. 	cout << dp[n] ;
  48. }
  49. _nhatminh{
  50. // 😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎
  51. freopen("");
  52. ios_base::sync_with_stdio(0);
  53. cin.tie(0); cout.tie(0);
  54. int q=1;
  55. // cin >> q;
  56. while (q--)
  57. 	solve();
  58. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  59. return (0);
  60. }
  61. /*cc*/
  62. /*
  63. Dưới ánh đèn mờ ảo, người lập trình C++ ngồi, Bàn phím rì rào, mã nguồn như dòng suối chảy trôi.
  64.  
  65. Với vòng lặp while, anh ta tạo nên thế giới, Đôi mắt sáng ngời, nhìn thấy sự sống trong dòng code.
  66.  
  67. Anh ta không ngừng, không mệt mỏi, không chùn bước, C++ trong tay, anh ta như một nhạc trưởng tài hoa.
  68.  
  69. Dù đêm đã khuya, dù ngày đã dài, anh ta vẫn tiếp tục, Vì trong lòng anh, C++ là niềm đam mê không thể ngăn cản.
  70.  
  71. Với mỗi dòng code, anh ta tạo ra một thế giới mới, C++ trong tay, anh ta là người hùng của thời đại số hóa.
  72. Trong tâm trí anh, mỗi biến là một vì sao sáng,
  73. Mỗi hàm số, một hành tinh, trong vũ trụ code rộng lớn.
  74.  
  75. Anh ta viết, anh ta xóa, anh ta sửa, anh ta tạo,
  76. C++ trong tay, anh ta như một họa sĩ đang vẽ tranh.
  77.  
  78. Mỗi lỗi code, một thách thức, một cơ hội để học hỏi,
  79. Anh ta không ngại khó khăn, vì anh biết đó là cầu nối.
  80.  
  81. Anh ta viết code, không chỉ vì công việc, mà còn vì đam mê,
  82. C++ trong tay, anh ta là người thợ rèn kiên trì.
  83.  
  84. Anh ta không chỉ viết code, anh ta còn tạo ra giá trị,
  85. C++ trong tay, anh ta là người thợ mài đá quý.
  86.  
  87. Anh ta không chỉ là một lập trình viên, anh ta còn là một người sáng tạo,
  88. C++ trong tay, anh ta là người đưa thế giới vào tương lai.
  89.  
  90. Với C++, anh ta có thể tạo ra những ứng dụng tuyệt vời,
  91. C++ trong tay, anh ta là người thợ rèn tương lai.
  92.  
  93. Anh ta không chỉ là một lập trình viên, anh ta còn là một người hùng,
  94. C++ trong tay, anh ta là người thợ rèn thế giới mới.
  95. */
  96. // tho by ai
Success #stdin #stdout #stderr 0.02s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
stderr
copy 
Time elapsed 0.015687s.
https://ideone.com/dXgshP
language:
C++14 (gcc 8.3)
created:
5 days 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!