fork(3) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long min(long long a, long long b) {
  5. 	if(a < b)
  6. 		return a;
  7. 	else
  8. 		return b;
  9. }
  10.  
  11. int main() {
  12. 	int t,n,k,p,current;
  13. 	cin>>t;
  14. 	while(t--) {
  15. 		cin>>n>>k>>p;
  16. 		int a[n+1];
  17. 		int b[n+1];
  18. 		long ans[n+1];
  19. 		long ans1[n+1];
  20. 		for(int i = 1; i <= n; i++) {
  21. 			ans[i] = 1000000000;	
  22. 			ans1[i] = 1000000000;	
  23. 			cin>>a[i];
  24. 		}
  25. 		for(int i =1; i <= n; i++) {
  26. 			cin>>b[i];
  27. 		}
  28. 		ans[0] = 0;
  29. 		current = 0;
  30. 		for(int i = 1; i <= n; i++) {
  31. 			for(int j= i-1 ; j >= i-k && j >= 0 ; j--) {
  32. 				if(j <= 0 && i > 1)
  33. 					continue;
  34. 				if(current ==0) {
  35. 					ans[i] = min(ans[i],ans[j] + a[i]);
  36. 					if(ans[j] + b[i] + p < ans[i]) {
  37. 						ans[i] = ans[j] + b[i] +p;
  38. 						current = 1;
  39. 					}
  40. 				}
  41. 				else {
  42. 					ans[i] = min(ans[i],ans[j] + b[i]);
  43. 					if(ans[j] + a[i] + p < ans[i]) {
  44. 						ans[i] = ans[j] + a[i] + p;
  45. 						current = 0;
  46. 					}
  47. 				}
  48. 			}
  49.  
  50. 		}
  51. 		ans1[0] = 0;
  52. 		current = 1;
  53. 		for(int i = 1; i <= n; i++) {
  54. 			for(int j= i-1; j >= i-k && j >= 0 ; j--) {
  55. 				if(j <= 0 && i > 1)
  56. 					continue;
  57.  
  58. 				if(current == 0) {
  59. 					ans1[i] = min(ans1[i],ans1[j] + a[i]);
  60. 					if(ans1[j] + b[i] + p < ans1[i]) {
  61. 						ans1[i] = ans1[j] + b[i] +p;
  62. 						current = 1;
  63. 					}
  64. 				}
  65. 				else {
  66. 					ans1[i] = min(ans1[i],ans1[j] + b[i]);
  67. 					if(ans1[j] + a[i] + p < ans1[i]) {
  68. 						ans1[i] = ans1[j] + a[i] + p;
  69. 						current = 0;
  70. 					}
  71. 				}
  72. 			}
  73. 		}
  74. 	cout<<min(ans[n],ans1[n])<<endl;
  75.  
  76. 	}
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
6
4 1 0 
1 2 3 4
1 2 3 4
4 1 0 
1 2 3 4
4 3 2 1
4 2 0 
1 2 3 4
4 3 2 1
4 1 10
1 2 3 4
4 3 2 1 
4 2 10
1 2 3 4
4 3 2 1 
5 1 50
0 0 102 104 0
101 103 0 0 105
stdout
copy 
10
6
4
10
7
100
https://ideone.com/Lpwu6I
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years 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!