fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const ll INF = ll(1e18);
  25. ll dp[5001][5001];
  26. ll a[5001];
  27. ll b[5001];
  28. int n; 
  29.  
  30. ll solve(int x, int y)
  31. {
  32. 	if(x == n && y == n) return 0;
  33. 	int turn = (x+y)&1; //odd means P2's turn, even means P1's turn
  34. 	if(dp[x][y] == -INF)
  35. 	{
  36. 		if(!turn)
  37. 		{
  38. 			ll ans = -INF;
  39. 			if(x < n)
  40. 			{
  41. 				ans = max(ans, a[x]+solve(x+1,y));
  42. 			}
  43. 			if(y < n)
  44. 			{
  45. 				ans = max(ans, b[y]+solve(x,y+1));
  46. 			}
  47. 			dp[x][y] = ans;
  48. 		}
  49. 		else
  50. 		{
  51. 			ll ans = INF;
  52. 			if(x < n)
  53. 			{
  54. 				ans = min(ans, -a[x]+solve(x+1,y));
  55. 			}
  56. 			if(y < n)
  57. 			{
  58. 				ans = min(ans, -b[y]+solve(x,y+1));
  59. 			}
  60. 			dp[x][y] = ans;
  61. 		}
  62. 	}
  63. 	return dp[x][y];
  64. }	
  65.  
  66. int main()
  67. {
  68. 	ios_base::sync_with_stdio(0); cin.tie(0);
  69. 	for(int i = 0; i < 5001; i++)
  70. 	{
  71. 		for(int j = 0; j < 5001; j++)
  72. 		{
  73. 			dp[i][j] = -INF;
  74. 		}
  75. 	}
  76. 	cin >> n;
  77. 	for(int i = 0; i < n; i++) cin >> a[i];
  78. 	for(int i = 0; i < n; i++) cin >> b[i];
  79. 	cout << solve(0, 0) << '\n';
  80. }
  81.  
Success #stdin #stdout 0.04s 198912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/RctAed
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!