fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. template<typename T>
  11. bool maximize(T& a, const T& b) {
  12. 	if (b < a) return false; 
  13. 	a = b; 
  14. 	return true; 
  15. }
  16.  
  17. const int N = 2e2 + 5; 
  18. const int M = 2e2 + 5;  
  19.  
  20. int dx[2] = {1, 0}; 
  21. int dy[2] = {0, 1}; 
  22.  
  23. int n, m;  
  24. int a[N][M];  
  25.  
  26. int what_subtask() {
  27. 	if (n <= 50 && m <= 50) return 2;  
  28. 	return 3;  
  29. }
  30.  
  31. bool inside(int x, int y) {
  32. 	return (1 <= x && x <= n && 1 <= y && y <= m); 
  33. }
  34.  
  35. bool corner(int x, int y) {
  36. 	return ((x == 1 && y == 1) || (x == n && y == m));   
  37. }
  38.  
  39. namespace sub2 {
  40. 	const int N = 55, M = 55;   
  41.  
  42. 	// dp[x1][y1][x2][y2] là tổng số điểm kinh nghiệm lớn nhất đạt được khi An đã đến ô (x1, y1) và Bình đã đến ô (x2, y2) 
  43. 	bool vis[N][M][N][M];  
  44. 	int memo[N][M][N][M];   
  45.  
  46. 	int dp(int x1, int y1, int x2, int y2) {
  47. 		if (!inside(x1, y1) || !inside(x2, y2)) return -INF;  
  48. 		if (x1 == 1 && y1 == 1 && x2 == 1 && y2 == 1) return 0;   
  49. 		if (!corner(x1, y1) && !corner(x2, y2) && x1 == x2 && y1 == y2) return -INF;   
  50.  
  51. 		int& ans = memo[x1][y1][x2][y2];  
  52. 		if (vis[x1][y1][x2][y2]) return ans;   
  53.  
  54. 		vis[x1][y1][x2][y2] = true;   
  55.  
  56. 		ans = -INF;   
  57. 		for (int i = 0; i < 2; i++) {
  58. 			for (int j = 0; j < 2; j++) {
  59. 				int prev_x1 = x1 - dx[i], prev_y1 = y1 - dy[i];   
  60. 				int prev_x2 = x2 - dx[j], prev_y2 = y2 - dy[j];    
  61. 				maximize(ans, dp(prev_x1, prev_y1, prev_x2, prev_y2) + a[x1][y1] + a[x2][y2]); 
  62. 			}
  63. 		}
  64.  
  65. 		return ans;  
  66. 	}
  67.  
  68. 	void solve() {
  69. 		memset(vis, 0, sizeof vis); 
  70.  
  71. 		cout << dp(n, m, n, m) << '\n'; 
  72. 	}
  73. }
  74.  
  75. namespace sub3 {
  76. 	// dp[x1][y1][x2][y2] là tổng số điểm kinh nghiệm lớn nhất đạt được khi An đã đến ô (x1, y1) và Bình đã đến ô (x2, y2) 
  77. 	// Ta có: 
  78. 	// 	   x1 + y1 = x2 + y2  
  79. 	// <=>    y2   = x1 + y1 - x2  
  80. 	// =>  y2 phụ thuộc vào 3 tham số còn lại
  81. 	// =>  chỉ cần lưu thông tin x1, y1, x2
  82.  
  83. 	bool vis[N][M][N];  
  84. 	int memo[N][M][N];   
  85.  
  86. 	int dp(int x1, int y1, int x2) {
  87. 		int y2 = x1 + y1 - x2; 
  88.  
  89. 		if (!inside(x1, y1) || !inside(x2, y2)) return -INF;  
  90. 		if (x1 == 1 && y1 == 1 && x2 == 1 && y2 == 1) return 0;   
  91. 		if (!corner(x1, y1) && !corner(x2, y2) && x1 == x2 && y1 == y2) return -INF;   
  92.  
  93. 		int& ans = memo[x1][y1][x2];  
  94. 		if (vis[x1][y1][x2]) return ans;   
  95.  
  96. 		vis[x1][y1][x2] = true;   
  97.  
  98. 		ans = -INF;   
  99. 		for (int i = 0; i < 2; i++) {
  100. 			for (int j = 0; j < 2; j++) {
  101. 				int prev_x1 = x1 - dx[i], prev_y1 = y1 - dy[i];   
  102. 				int prev_x2 = x2 - dx[j];    
  103. 				maximize(ans, dp(prev_x1, prev_y1, prev_x2) + a[x1][y1] + a[x2][y2]); 
  104. 			}
  105. 		}
  106.  
  107. 		return ans;  
  108. 	}
  109.  
  110. 	void solve() {
  111. 		memset(vis, 0, sizeof vis); 
  112.  
  113. 		cout << dp(n, m, n) << '\n'; 
  114. 	}
  115. }
  116.  
  117.  
  118. int main() {
  119. 	ios::sync_with_stdio(0); cin.tie(0);  	
  120. 	cin >> n >> m;  
  121.  
  122. 	for (int i = 1; i <= n; i++) {
  123. 		for (int j = 1; j <= m; j++) cin >> a[i][j]; 
  124. 	}
  125.  
  126. 	int subtask = what_subtask(); 
  127. 	if (subtask == 2) sub2::solve(); 
  128. 	if (subtask == 3) sub3::solve(); 
  129. }
Success #stdin #stdout 0.01s 17612KB
comments (?)
stdin
copy 
3 3
0 2 3
4 5 6
7 8 0
stdout
copy 
32
https://ideone.com/w7mvZ0
language:
C++14 (gcc 8.3)
created:
1 year 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!