fork download
copy 
  1. using namespace std;
  2.  
  3. #include <iostream>
  4. #include <fstream>
  5. #include <vector>
  6. #include <algorithm>
  7.  
  8. #define MOD 1000000007
  9.  
  10. vector<pair<int,bool>> v; 
  11.  
  12. long long dp[1005][2];
  13. bool arr[1005][2];
  14.  
  15. int main() {
  16. 	int R,B,L;
  17. 	cin >> R >> B >> L;
  18.  
  19. 	for(int i = 0;i < R + B;++i) {
  20. 		int cur;
  21. 		cin >> cur;
  22. 		if(i < R) {
  23. 			arr[cur][0] = true;
  24. 		}else{
  25. 			arr[cur][1] = true;
  26. 		}
  27. 	}
  28. 	dp[0][0] = 1;
  29. 	dp[0][1] = 1;
  30.  
  31. 	for(int i = 1;i <= 1000;++i) {
  32. 		if(arr[i][0] && arr[i][1]) {
  33. 			for(int j = L - i;j >= 0;--j) {
  34. 				dp[j + i][0] += dp[j][1];
  35. 				if(dp[j + i][0] >= MOD) dp[j + i][0] -= MOD;
  36. 				dp[j + i][1] += dp[j][0];
  37. 				if(dp[j + i][1] >= MOD) dp[j + i][1] -= MOD;
  38. 				if(j + 2 * i <= L) {
  39. 					dp[j + 2 * i][0] += dp[j][0];
  40. 					if(dp[j + 2 * i][0] >= MOD) dp[j + 2 * i][0] -= MOD;
  41. 					dp[j + 2 * i][1] += dp[j][1];
  42. 					if(dp[j + 2 * i][1] >= MOD) dp[j + 2 * i][1] -= MOD;
  43. 				}
  44. 			}
  45. 		}else if(arr[i][0] && !(arr[i][1])) {
  46. 			for(int j = L - i;j >= 0;--j) {
  47. 				dp[j + i][0] += dp[j][1];
  48. 				if(dp[j + i][0] >= MOD) dp[j + i][0] -= MOD;
  49. 			}
  50. 		}else if(!(arr[i][0]) && arr[i][1]) {
  51. 			for(int j = L - i;j >= 0;--j) {
  52. 				dp[j + i][1] += dp[j][0];
  53. 				if(dp[j + i][1] >= MOD) dp[j + i][1] -= MOD;
  54. 			}
  55. 		}
  56. 	}
  57. 	cout << (dp[L][0] + dp[L][1]) % MOD << endl;
  58. }
Runtime error #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mCVCuV
language:
C++14 (gcc 8.3)
created:
4 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!