fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <stack>
  6. #include <algorithm>
  7. #include <cstdio>
  8.  
  9. using namespace std;
  10.  
  11. long long int A[5010],B[5010];
  12. long long int dp[5010][5010];
  13. int N;
  14.  
  15. long long int maxi(int x, int y);
  16.  
  17. long long int mini(int x, int y) {
  18. 	if(dp[x][y]) {
  19. 		return dp[x][y];
  20. 	}
  21. 	if(x==N && y == N) {
  22. 		return 0;
  23. 	}
  24. 	long long int ans = 1e18;
  25. 	if(x<N) {
  26. 		ans = (-A[x] + maxi(x+1,y));
  27. 	}
  28. 	if(y<N) {
  29. 		ans = min(ans, -B[y] + maxi(x, y+1));
  30. 	}
  31. 	dp[x][y]= ans;
  32. 	return ans;
  33. }
  34.  
  35. long long int maxi(int x, int y) {
  36. 	if(dp[x][y]) {
  37. 		return dp[x][y];
  38. 	}
  39. 	if(x == N && y == N) {
  40. 		return 0;
  41. 	}
  42. 	long long int ans = -1e18;
  43. 	if(x<N) {
  44. 		ans = (A[x] + mini(x+1, y));
  45. 	}
  46. 	if(y<N) {
  47. 		ans = max(ans, B[y] + mini(x, y+1));
  48. 	}
  49. 	dp[x][y]= ans;
  50. 	return ans;
  51. }
  52.  
  53. int main() {
  54. 	cin>>N;
  55. 	for(int i = 0; i < N; i++) {
  56. 		cin>>A[i];
  57. 	}
  58. 	for(int j = 0; j < N; j++) {
  59. 		cin>>B[j];
  60. 	}
  61. 	cout<<maxi(0,0)<<endl;
  62.  
  63. }
  64.  
Success #stdin #stdout 0s 199616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YYX7Jh
language:
C++14 (gcc 8.3)
created:
7 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!