fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4. bool can[10001],last[10001];
  5. int main() {
  6. 	int n;
  7. 	cin>>n;
  8. 	while(n--){
  9. 		memset(can,0,sizeof(can));
  10. 		memset(last,0,sizeof(last));
  11. 		int t,k,max,step[100];
  12. 		bool hole[10001] = {},yes = 0;
  13. 		cin>>t>>k>>max;
  14. 		for(int i=0;i<t;i++)
  15. 			cin>>step[i];
  16. 		for(int i=0;i<k;i++){
  17. 			int x;
  18. 			cin>>x;
  19. 			hole[x] = 1;
  20. 		}
  21. 		can[0] = 1;
  22. 		bool *now = can,*before = last;
  23. 		for(int i=0;i<t;i++){
  24. 			memset(before,0,sizeof(can));
  25. 			for(int j=0;j<=10000;j++){
  26. 				if(now[j]){
  27. 					int next = j+step[i];
  28. 					if(next<=max&&!hole[next]){
  29. 						before[next] = 1;
  30. 					}
  31. 					next = j-step[i];
  32. 					if(next>0&&!hole[next])
  33. 						before[next] = 1;
  34. 				}
  35. 			}
  36. 			bool *temp = now;
  37. 			now = before;
  38. 			before = temp;
  39. 		}
  40. 		for(int i=max;i>0;i--){
  41. 			if(now[i]){
  42. 				cout<<i<<endl;
  43. 				yes = 1;
  44. 				break;
  45. 			}
  46. 		}
  47. 		if(!yes)
  48. 			cout<<"-1"<<endl;
  49. 	}
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 16088KB
comments (?)
stdin
copy 
3
5 2 20
3 1 3 1 3
7 17
5 2 20
3 3 1 2 4
8 13
5 2 20
4 4 5 4 4
2 15
stdout
copy 
9
11
13
https://ideone.com/rXo77z
language:
C++ (gcc 8.3)
created:
6 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!