fork download
copy 
  1. // ashish_arora   
  2. #include <bits/stdc++.h>
  3. #define MOD 1000000007
  4. #define INF INT_MAX
  5. #define ll long long
  6. #define ld long double
  7. #define pb push_back
  8. #define all(c) c.begin() , c.end()
  9. #define IOS ios_base::sync_with_stdio(false);  cin.tie(NULL);
  10. using namespace std;
  11.  
  12. vector <int> lol;
  13.  
  14. int main(){
  15.  
  16. 	int n;
  17. 	cin >> n;
  18. 	int a[n];
  19. 	int b[n];
  20.  
  21. 	for (int i = 0 ; i < n ; i ++){
  22. 		cin >> a[i];
  23. 	}
  24.  
  25. 	for (int i = 0 ; i < n ; i ++){
  26. 		cin >> b[i];
  27. 	}
  28.  
  29. 	int dp[1001][n+1][n+1][2];
  30.  
  31. 	for (int z = 0 ; z <= 1000 ; z ++){
  32. 		for (int i = 0 ; i<= n ; i++){
  33. 			for (int j = 0 ; j <=n ; j ++){
  34. 				dp[z][i][j][1] = 0;
  35. 				dp[z][i][j][0] = 0;
  36. 				if (i == 0 || j == 0){
  37. 					dp[z][i][j][1] = 0;
  38. 					dp[z][i][j][0] = 0;
  39. 					// continue;
  40. 				}
  41. 				else{
  42. 					dp[z][i][j][1] = max(dp[z][i-1][j][1] , dp[z][i][j-1][1]);
  43. 					dp[z][i][j][0] = max(dp[z][i-1][j][0] , dp[z][i][j-1][0]);
  44. 					if (a[i-1] + z == b[j-1]){
  45. 						dp[z][i][j][1] = max(dp[z][i][j][1] , 1 + dp[z][i-1][j-1][1]);
  46. 					}
  47. 					if (a[i-1] == b[j-1] + z){
  48. 						dp[z][i][j][0] = max(dp[z][i][j][0] , 1 + dp[z][i-1][j-1][0]);
  49. 					}
  50.  
  51. 				}
  52.  
  53.  
  54. 			}
  55. 		}
  56. 	}
  57.  
  58. 	int mx = -INF;
  59. 	int diff = 0;
  60. 	bool cond = 0;
  61. 	for (int i = 0 ; i<= 1001 ; i ++){
  62. 		if (mx < dp[i][n][n][0]){
  63. 			mx = dp[i][n][n][0];
  64. 			diff = i;
  65. 			cond = 0;
  66. 		}
  67. 		if (mx < dp[i][n][n][1]){
  68. 			mx = dp[i][n][n][1];
  69. 			diff = i;
  70. 			cond = 1;
  71. 		}
  72.  
  73. 	}
  74.  
  75.  
  76. 	for (int i = 0 ; i <=n ; i ++){
  77. 		for (int j = 0 ; j<=n; j ++){
  78. 			cout << dp[diff][i][j][cond] << " ";
  79. 		}
  80. 		cout << endl;
  81. 	}
  82.  
  83.  
  84. 	int itr = n;
  85. 	int it = n;
  86. 	while(itr > 0 && it > 0){
  87. 		if (dp[diff][itr][it][cond] == dp[diff][itr-1][it][cond]){
  88. 			itr --;
  89.  
  90. 		}else if (dp[diff][itr][it][cond] == dp[diff][itr][it-1][cond]){
  91. 			it --;
  92. 		}else if (dp[diff][itr][it][cond] > dp[diff][itr-1][it-1][cond]){
  93. 			lol.pb(a[itr-1]);
  94. 			itr -- ;
  95. 			it --;
  96. 		}
  97. 	}
  98.  
  99.  
  100. 	// reverse(lol.begin() , lol.end());
  101. 	// cout << lol.size() << endl;
  102. 	// if (cond){
  103. 	// 	for (int i = 0 ; i < lol.size() ; i++){
  104. 	// 		cout << lol[i] - diff << " ";
  105. 	// 	}
  106. 	// 	cout << endl;
  107. 	// 	for (int i = 0 ; i < lol.size() ; i++){
  108. 	// 		cout << lol[i]  << " ";
  109. 	// 	}
  110. 	// 	cout << endl;
  111.  
  112. 	// }
  113. 	// else{
  114.  
  115. 	// 	for (auto u: lol){
  116. 	// 		cout << u << " " ;
  117. 	// 	}
  118. 	// 	cout << endl;
  119.  
  120. 	// 	for (auto u : lol){
  121. 	// 		cout << u - diff  << " ";
  122. 	// 	}
  123. 	// 	cout << endl;
  124. 	// }
  125.  
  126.  
  127.  
  128.     return 0;
  129. }
Time limit exceeded #stdin #stdout 5s 4188KB
comments (?)
stdin
copy 
7
3 8 4 23 9 11 28  
2 3 22 26 8 16 12
stdout
copy 
3 26 16 -1406459119 8 23 11 22042 
11064 0 32767 0 0 7 32767 0 
0 32767 7 -1406459119 11064 0 22042 32767 
0 0 22042 11064 -1 32767 1 22042 
0 -470230060 22042 32767 0 0 -1338858487 431815283 
0 0 0 32767 11064 11064 0 0 
22042 32767 0 22042 32767 0 0 32767 
0 32767 32767 32767 32767 32767 32767 32767
https://ideone.com/G6xeY5
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!